JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Binary Search tutorial Binary search on real numbers
 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.. :)
 Forums Tutorial Discussions Binary Search tutorial Binary search on real numbers Previous Thread  |  Next Thread