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 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. It was reported to Sun recently when it broke someone's program, after lying in wait for nine years or so.
“Official Google Research Blog: Extra, Extra—Read All About It: Nearly All Binary Searches and Mergesorts are Broken [1]”
Back in November I was working on a program where I needed a binary search that not only returned if I found something, but where it was, or would be if found. I had written such code for my greylist daemon [2] so I lifted the code from there. As I was reusing the code, I realized that there indeed, could be a potential problem with it, in that a calculation of a certain value could overflow and cause unpredictable behavior.
But while I recognized the problem, I neglected to fix the problem in the greylist daemon [3]. And I completely forgot about it until I came across the blog post “Official Google Research Blog: Extra, Extra— Read All About It: Nearly All Binary Searches and Mergesorts are Broken [4].
Oops.
Anyway, the patch was a one line change, from
>
```
mod = (low + high) / 2;
```
to
>
```
mid = low + ((high - low) / 2);
```
The old code certainly worked, but there could be a chance, if the indicies low and high were significantly large enough, to overflow and cause undefined behavior. Truth be told, both high and low would have to be above 2,000,000,000 (on a typical system) before you might even get bit by this bug.
But still, the potential exists, and why not if it's an easy fix.
And all this is to announce the latest version [5] of the greylist daemon [6] (the “Beefier Bsearch [7]” version if you will).
[1] http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-
[4] http://googleresearch.blogspot.com/2006/06/extra-extra