### arftdipto's blog

By arftdipto, history, 15 months ago, Can anyone suggest me a good blog for binary search on double ? I found these type of implementation on different blog but failed to manage explanation. Could anyone explain it please ?

Type 1:

#include<bits/stdc++.h>
using namespace std;

//We want to find an element which a<0.0000001

const float target = 0.0000001;

int main()
{
float l=0.00000000,r=100000.00000000;
cout << l << " " << r;
while((r-l)>0.0000000001){
float mid = (float)((l+r)/2);
cout << mid << endl;
if(mid>target) r=mid;
else l=mid;
}cout << l;
}


Type 2:

int iterations = 0;
while(iterations < 300)
{
iterations++;
}  Comments (11)
 » Auto comment: topic has been updated by arftdipto (previous revision, new revision, compare).
 » Auto comment: topic has been updated by arftdipto (previous revision, new revision, compare).
 » This one is good
•  » » thanks
 » Thanks :D
 » Pashka goes into a lot of detail regarding the implementation issue you raised in your post. Look at his posts on EDU Binary Search. I suffered from the same EPS nightmare until I went through his tutorials.First register for the EDU. Then: Link for the post
•  » » Do you know why 100 iterations will always be sufficient?
•  » » » Because the maximal value for $long \space long$ is $2^{63}-1$. Even though binary search works in $O(\log n)$, there is not estimated value.Simple binary search on array for finding specific value may do more operations than exact $\log n$ value. For example, $a = [1, 3, 4, 7, 9, 14], \space x = 7$ does 3 operations, while $\log 6 = 2$. Since, this is very small testcase, the difference is small too.
•  » » » » Can you explain with refernce to real numbers?
•  » » » » » let us say I want to search for a number in a range of width W. x lies somewhere in the range [0,W]. If I were to choose any random number in this range then max error possible is W. Everytime I choose the midpoint of the range and will discard a range with width exactly half of the current search range.Now width of search range after 1 iteration is W/2, so max error possible is W/2.After K-iterations max error possible is W/(2^(K-1))
•  » » » » » » Thanks for this