(This should be all over the net by now. I first saw it here.)
Joshua Bloch: I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested 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. Lest you think I'm picking on Bentley, let me tell you how I discovered the bug: The version of binary search that I wrote for the JDK contained the same bug.
The bug is in this line:
6: int mid = (low + high) / 2;
Once pointed out, it's obvious what the problem is. Joshua called on everybody to fix such broken code before they blow up.
The question is: how? The scope could be huge—it includes every line of code ever written and put into production. If you are thinking "That's the scope of the Y2K problem," you are exactly right.
Fellow programmers, we have a "Low+High" problem at our hands. Somebody better mobilize an army of "Low+High" special forces and get working.
Previous Topic
