What’s wrong with binary search!


There’s a bug in the code of “Binary Search” as most of us write it. When asked most of us code binary search as -

int binary_search(int *a, int len, int key)
{
int low = 0;
int high = len-1;

while (low <= high)
{
int mid = (low+high)/2;
int val = a[mid];

if (val < key)
{
low = mid + 1;
} else if (val > key)
{
high = mid - 1;
} else
{
return mid;
}
}
return -1;
}

Now, try to find the bug in the above code. The bug surfaces if the array is too large. If the length of the array is too large, line number 8 in the above code would cause the variable “mid” to overflow and hence will have a negative number and the code breaks. A very simple solution would be to replace line 8 in the above code with -

mid = low + (high-low)/2;

So, you see how bugs could creep in your code. To see more detailed discussion on how the bug was discovered and a couple of more elegant, efficient solutions check out this Google Research blog – http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Loading Facebook Comments ...

7 thoughts on “What’s wrong with binary search!

  1. spsneo Post author

    @Vaibhaw

    Thanks for pointing out the bug. The variable name passed as parameter was different from the one being used in the function. I have updated the bug.

  2. Satyajeet

    Really a nice bug that we generally miss it.

    Thanx for pointing it out..:)

    Nice point:-
    A bug can exist for half a century despite our best efforts to exterminate it. We must program carefully, defensively, and remain ever vigilant.

  3. Satyajeet

    @Nipun,

    There is bug in your solution.
    It wudn’t work when both low and high are odd numbers.

    let’s say: low = 3 and high = 7
    mid should be (3 +7)/2 = 5. I mean (3 + 7) >> 1 :P

    A/c to ur solution:

    mid = 3/2 + 7/2 = 1 + 3 = 4 (wrong)

Leave a Reply