JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Binary search on real numbers | Reply
In the tutorial, which is great, the author gives the following algorithm for doing a binary search on real numbers:
binary_search(lo, hi, p) {
   while we choose not to terminate:
      mid = lo + (hi-lo)/2
      if p(mid) == true:
         hi = mid
      else:
         lo = mid
          
   return lo // lo is close to the border between no and yes
}

My question is on the last line of the algorithm. The author states that "lo is close to the border between no and yes", but I don't understand why this is. Intuitively, it seems like mid would be a better value to return. Or maybe it doesn't matter since low, mid, and high are so close in value at this time. I would appreciate some comments and clarification.
Re: Binary search on real numbers (response to post by michaelrpg) | Reply
well, the point of the loop is to reduce the error as much as possible. When the algorithm ends, the error is supposed to be negligible so in reality, assuming that your algorithm is correct, lo,mid and hi should be indistinguishable for practical purposes.
Re: Binary search on real numbers (response to post by vexorian) | Reply
I think we should do
if(p(mid)==true)
"hi=mid-1;"
instead of "hi="mid";
This will reduce the search space. I know doing this will not largely affect the time complexity coz of being logarithmic but still.Am i wrong at it?
Re: Binary search on real numbers (response to post by mohit_verma) | Reply
ohh i got it now.
Re: Binary search on real numbers (response to post by mohit_verma) | Reply
no.. for real number it should be "hi=mid" not "hi=mid-1".. how about if our answer is mid-0.0005 ? if we do "hi=mid-1" then we won't get our answer.. :)
RSS