tough-to-explain Python

[Terry Reedy]

Steven D'Aprano wrote:

> And speaking of binary search:
> 
> [quote]
> I was shocked to learn that the binary search program that Bentley PROVED 
> CORRECT and SUBSEQUENTLY TESTED [emphasis added] in Chapter 5 of 
> "Programming Pearls" contains a bug. Once I tell you what the it is, you 
> will understand why it escaped detection for two decades.
> [end quote]
> 
> http://northernplanets.blogspot.com/2006/07/nearly-all-binary-searches-are-broken.html
> 
> or http://tinyurl.com/nco6yv

The actual report is at
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

The is the so called bug:
"In Programming Pearls Bentley says that the analogous line "sets m to 
the average of l and u, truncated down to the nearest integer." On the 
face of it, this assertion 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 (231 
- 1). The sum overflows to a negative value, and the value stays 
negative when divided by two. In C this causes an array index out of 
bounds with unpredictable results. In Java, it throws 
ArrayIndexOutOfBoundsException."

The is *not* a bug is Bentley program. It is a bug in bad, buggy, insane 
integer arithmetic implementations. low + high should either return the 
right answer, as it will in Python, or raise an overflow error.

tjr