Google Research Blog: Nearly All Binary Searches and Mergesorts are Broken [2006] | Hacker News Reader

Google Research Blog: Nearly All Binary Searches and Mergesorts are Broken [2006]

googleresearch.blogspot.com

Not just binary search. Anything that involves addition of signed integers could overflow.

Including, as I found to my embarassment recently, my license key generation logic.

Turns out that the maximum for a Java integer happens in the middle of the numerical representations of the values that I thought were valid license keys. "Whoops!"

(Happily, it turns out that all the keys actually assigned to customers were accepted by the broken version of the checker, too.)

The bug is an example of a problem associated with inductive inference. Relying on induction is tempting, and in most cases sufficient. However, this case proves that one should always be aware of the potential fallacy that is inherent in induction.

or at least be aware that one is doing modulo arithmetic.

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

is going to overflow if high and low have different signs. The correct version that works for any high and low is:

  int mid = sign(high) != sign(low) ?
    (high + low) / 2 : low + (high - low) / 2;

True, but Java uses signed int's so the former should still work.

That's the problem, if one int is negative and the other is positive, (high - low) may overflow.

In this particular context, however, that should be just fine: low is clearly initialized to zero, and then only set to the value of this expression +1. As such, barring other bugs, low can never be negative.

Your point is valid, though, and worth bearing in mind in other circumstances.

I think a static checker such as Coverity would probably find this bug.

Reply on news.ycombinator.com