R.A.X's blog

Problem in Binary Search
By R.A.X, 10 years ago, In English

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??

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. mid = low + (high — low) / 2 — wrong.
    mid = (low + high) / 2 — correct.
  2. if (ans > m) high = mid — 1 — wrong.
    if (ans > m) high = mid — correct.
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    (low + high) / 2 = low + (high — low) / 2

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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 :).

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    +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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I will keep this in mind next time.

    → Reply