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