5 ms·
Google Research Blog: Nearly All Binary Searches and Mergesorts are Broken [2006]
- jollojou 17y agoThe 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.
- swolchok 17y agoor at least be aware that one is doing modulo arithmetic.
- bigbang 17y agoNot just binary search. Anything that involves addition of signed integers could overflow.
- patio11 17y agoIncluding, 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.)
- mojuba 17y agoint 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;
- stuff4ben 17y agoTrue, but Java uses signed int's so the former should still work.
- mojuba 17y agoThat's the problem, if one int is negative and the other is positive, (high - low) may overflow.
- amalcon 17y agoIn 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.
- jderick 17y agoI think a static checker such as Coverity would probably find this bug.