Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Binary Searching for nearest float value

Posted on 2004-08-12
9
Medium Priority
?
541 Views
Last Modified: 2012-06-27
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?
0
Comment
Question by:keepthursdayspecial
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
  • 2
9 Comments
 
LVL 44

Expert Comment

by:Arthur_Wood
ID: 11783403
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
 
LVL 44

Expert Comment

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

AW
0
 

Author Comment

by:keepthursdayspecial
ID: 11783701
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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 

Author Comment

by:keepthursdayspecial
ID: 11783721
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 Comment

by:keepthursdayspecial
ID: 11783914
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
 
LVL 11

Expert Comment

by:lbertacco
ID: 11783928
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
 
LVL 11

Accepted Solution

by:
lbertacco earned 500 total points
ID: 11783952
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
 
LVL 11

Expert Comment

by:lbertacco
ID: 11784257
...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 Comment

by:keepthursdayspecial
ID: 11784649
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

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Make the most of your online learning experience.
What do responsible coders do? They don't take detrimental shortcuts. They do take reasonable security precautions, create important automation, implement sufficient logging, fix things they break, and care about users.
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…

618 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question