### R.A.X's blog

By R.A.X, 10 years ago,

I am implementing a simple binary search.But my program is not giving the correct solution on some values. long long low=1,high=100000000000000,mid=0,ans=0;
while ( high > low)
{
mid =low +(high-low)/2;
ans=mid;
if( ans==m )
return ans;
if (ans > m)
high=mid-1;
else
low=mid+1;
} return low;

This binary search should return the value equal to m,But this is failing on most of the cases. Can anyone tell me the mistake??

• -12

 » 10 years ago, # |   0 mid = low + (high — low) / 2 — wrong. mid = (low + high) / 2 — correct. if (ans > m) high = mid — 1 — wrong. if (ans > m) high = mid — correct.
•  » » 10 years ago, # ^ |   +1 (low + high) / 2 = low + (high — low) / 2
 » 10 years ago, # |   0 You should change the following parts and it should be fine low=1,high=100000000000000,mid=0,ans=0; while ( high >= low){ mid =low +(high-low)/2; ans = mid; if( ans == m ) return mid; if (ans > m) high = mid-1; else low = mid+1; } // Not Found return -1; However, I guess that most of the time you want ans = f(mid)
 » 10 years ago, # | ← Rev. 2 →   +5 Your mistake is that you ask such a question here.I'd advise you to run your code step-by-step with the help of a debugger. This should be much more useful than if somebody will point to your error.UPD. But I'm late, you got your hint. You've lost a small, but valuable lesson :).
•  » » 10 years ago, # ^ | ← Rev. 2 →   +3 +1, but running binary search step-by-step didn't helped me a lot, but online lecture did. There was a rule you must grant for l,r. Here is total idea. // x c [1;15]; // f(x) = 0,0,0,0,1,1,1,2,2,2,2,2,3,3,3 // I need to find "x" such that f(x) = 2 // lower or upper bound? // "resulting x will be in (l;r]" <- I've granted this rule to find lower bound int l = 0, r = 15; // l is out of [1;15] because of my rule, resulting x may be "1" while( l+1 < r ) { int x = l + (r-l)/2; if( f(x) < 2 ) l = x; // value of "x" is defenetly not what we are looking for, let it be "l" in (l;r] else r = x; // f(x) >= 2, but we're interested in lower bound // our answer is still in (l;r] } // now our segment (l;r] is (7;8], so 8 is the lower bound if( f(r) == 2 ) cout << "FOUND"; else cout << "NOT FOUND"; // now it's simple to find upper bound, just grant a rule [l;r) and choose right initial vals try it on ideone
•  » » » 10 years ago, # ^ |   +3 thanks Got it!!!
•  » » 10 years ago, # ^ |   +3 I will keep this in mind next time.