Best way to determine which array item is closest to a value

[Traxus]

This is a hard one to explain but lets say I've got an array of values that share no rhythm with one another, a:

Code: Select all

decl a;

a[1]=500;
a[2]=750;
a[3]=1000;
a[4]=2500;
a[5]=4500;

Now I've got another value, b, and I want to know which item within a has the value closest value...

Code: Select all

decl b;
decl c;

b = 550;
c = getclosest(a, b); //should yeild a[1] or 500

b = 874;
c = getclosest(a, b); //should yeild a[2] or 750

What is the best definition for 'getclosest()'? Am I stuck writing a loop with a conditional?

[kisslorand]

Something like this:

Code: Select all

decl index;
decl closeness;
index=0;
closeness=abs(a[0]-b);
for (i=0; i<sizeof(a); i++)
   if (abs(a[i]-b) < closeness)
   {
      closeness=abs(a[i]-b);
      index=i;
   }
return(a[index]);

This algo finds the first element which is closest to "b" if you have two of them (like 250 and 750 compared to 500), if you want to find the latest, you should put "<=" in the if condition.

[Traxus]

Thanks, that's what I had in mind, I was just wondering if there was a less expensive way to do it as I was considering employing this in an onframe script which could get hairy especially with larger arrays.

[kisslorand]

For the infos you gave, that's the only solution. You have a generic solution for a generic problem. If your array is arranged, you can try the bubble algorithm, if not arranged, you should verify closeness upon every array element change... and so on.

[Macciza]

Hi

If you expect the value to sometimes be identical you could add

if(firstof((a/b)==1)!=sizeof(a))return (a[firstof((a/b)==1)]); // if val matches return it . ..

after the initial declarations to return the matching value without iterating . . .

MM

[Traxus]

Thanks again guys

Still bouncing this around my head, I was hoping for some magic inverse of php/c++ array_key_exists() but the now that I think about it, iterating is still the cheapest and only way.

I might have to forego this as running it on frame sounds like more of a headache than it is worth, and at best i would be running it on expression which would be tied to the x value of a knob that could be firing the script pretty rapidly anyway...

Still toying with the idea of inverting the array to something like this:

Code: Select all

decl a;

a[500]=1;
a[750]=1;
a[1000]=1;
a[2500]=1;
a[4500]=1;

And then, as x changes, checking if the array key is set to 1, or if it is null/0... That way when x passes a value that exists I can flag that as the 'closest' value even though it isn't technically the closest (but at worse is the second closest value which may be enough for my application)