Free Software programmer
This blog existed before my current employment, and obviously reflects my own opinions and not theirs.
This work is licensed under a Creative Commons Attribution 2.1 Australia License.
Tue, 06 Jun 2006
Via Miguel de Icaza's blog I read a Google researcher saying Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken .
The problem is an overflow in adding the high and low indices to calculate the midpoint, apparently widely implemented as in Programming Pearls . I'm not a Java person, but fortunately he has a C fix, too.
This is classic programmer behavior: find a problem, patch it, declare it fixed. But the root of this problem has been missed, with two consequences: (1) people reading this are mislead as to the cause of this problem, and (2) the problem immediately behind it still lurks, at least in C.
The suggested C fix is: "mid = ((unsigned) (low + high)) >> 1;".
The better fix is to realize that valid indices into
Now the next problem becomes apparent: we've just shifted the overflow from 31 bits to 32 bits, giving ourselves a bugfix which will last ~10 months. low=1,200,000,000 high=1,200,000,100 works now, but low=2,400,000,000 high=2,400,000,100 still doesn't. There are several fixes for this, mine is here.
 For all I know, Java can't handle arrays of length > 31 bit, making this overkill, but C certainly can.
[/tech] permanent link