# Binary Searching for nearest float value

I have a float array representing distance bins from 1.5 to 23.5 at 0.5 increments.  I am trying to find the nearest float using a binary search so that if, for example, i have a distance of 18.76 the search returns the index of the array containing value 18.5.

Here is what i have so far but this seems to skip counts at the mid-point distances:

int nearest(float array[], const int nbins, const float value, const float binwidth)
{
float dx;
int mid;
int lowest = 0;
int highest = nbins - 1;

while (lowest <= highest)
{
mid = (lowest + highest) / 2;
dx = value - array[mid];

// if the midpoint value is the closest
if ( (dx < binwidth) && (dx >= 0.0) )
return mid;

if (dx < 0.0)
highest = mid - 1;
else
lowest  = mid + 1;
}
cout << "Failed finding: " << value << endl;
return -1;
}

Any ideas?
###### Who is Participating?

Commented:
Ok than for arbitrary resolution r (0.1 .. 5), with l=lowest bin (which if I understand correctly is array[0]), just do:

index=floor((value-l)/r+.5);
if(index>=nbins) index=nbins-1;

or, if you want to round down (instead of round to the nearest):

index=floor((value-l)/r);
if(index>=nbins) index=nbins-1;
0

Commented:
since your increments are exactly 0.5 - multiply the test value (say it is 18.76), by 2, make THAT value an Integer, and then divide by 2:

18.76 * 2 = 37.52  ---> 37  /2 = 18.5  this will return the Largest increment value that is SMALLER than the Test value.

AW
0

Commented:
is it a requirement that you use a Binary search - in which case this sounds like a Homework assignment, to me.

AW
0

Author Commented:
no it is not a requirement but i'll be be performing the search around 20,000 to 30,000 times over the course of the program.  I'm working on a biophysics problem for protein structure.  Is there a faster method for doing this I don't know about?
0

Author Commented:
In addition, the increments are not always 0.5.  They can vary between 0.1 up to 5 depending on the resolution level required.
0

Author Commented:
In addition, the increments are not always 0.5.  They can vary between 0.1 up to 5 depending on the resolution level required.
0

Commented:
To find the NEAREST float (and not the greater float lower or equal to value), and assuming your array is sorted (otherwise binary search is not a good idea)  you can do this:

while (lowest <= highest) {
mid = (lowest + highest) / 2;
if(value>array[mid]) lowest=mid+1;
else highest=mid-1;
}
//now we have highest=lowest-1 and we just choose either one
if(highest<0) return lowest;
else if(lowest>=nbins) return highest;
else return (value-array[highest]>array[lowest]-value) ? lowest : highest;

This works with arbitrary float values for distance bins. If you already know that you have all values from 1.5 to 23.5 at .5 increment you can just do:

index=floor((value-array[0])*2+0.5);
if(index>=nbins) index=nbins-1;

with no need for binary search.
0

Commented:
...if you are not guaranteed that value is always greater or equal to l (array[0]) than you should check for this condition too (otherwise you might get a negative index)
0

Author Commented:
The index will never be less than zero as i'm calculating atomic distances which will always be absolute.

Thanks very much for these solutions.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.