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
There is one more bug
, try to find one 
@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.
Neat.
or you could be careless and still use a BigNum library like GMP.
Apparently
mid = lo/2 + hi/2;
would be more more efficient (two shifts, one sum)
@Nipun
Google Research blog suggested a better way (one sum and one shift).
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.
@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
A/c to ur solution:
mid = 3/2 + 7/2 = 1 + 3 = 4 (wrong)