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?
keepthursdayspecialAsked:
Who is Participating?

Improve company productivity with a Business Account.Sign Up

x
 
lbertaccoConnect With a Mentor 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
 
Arthur_WoodCommented:
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
 
Arthur_WoodCommented:
is it a requirement that you use a Binary search - in which case this sounds like a Homework assignment, to me.

AW
0
What Kind of Coding Program is Right for You?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

 
keepthursdayspecialAuthor 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
 
keepthursdayspecialAuthor 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
 
keepthursdayspecialAuthor 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
 
lbertaccoCommented:
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
 
lbertaccoCommented:
...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
 
keepthursdayspecialAuthor 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.

All Courses

From novice to tech pro — start learning today.