Bug in Binary Search after twenty years

The bug is in this line:

5: int mid =(low + high) / 2;

The above line of code suggest that it sets mid to average value of low and high,trucated down to the nearest integer.It might appear correct,but it fails for large values of the int variables low and high.Specifically, it fails if the sum of low and high is greater than the maximum positive int value (2^31 - 1).The sum overflows to a negative value, and the value stays negative when divided by two.

Errors:
In "C" this causes an array index out of bounds with unpredictable results.
In "Java",it throws ArrayIndexOutOfBoundsExce ption.

So what's the best way to fix the bug? Here's one way:

5: int mid = low + ((high - low) / 2);

Probably faster, and arguably as clear is:

5: int mid = (low + high) >>> 1;

In C and C++ (where you don't have the >>> operator), you can do this:

5: mid = ((unsigned) (low + high)) >> 1;

The binary-search bug applies equally to mergesort, and to other divide-and-conquer algorithms. If you have any code that implements one of these algorithms, fix it now before it blows up. The general lesson that I take away from this bug is humility: It is hard to write even the smallest piece of code correctly, and our whole world runs on big, complex pieces of code.