A tale from the Monk's Inn

The Monk's Inn was a restaurant, now long closed, on Manhattan's Upper West Side. Once upon a time I had dinner there with a friend of mine and a friend of his, who was one of a large computer company's leading experts in sorting.

He made what seemed a remarkable claim: He had never seen a published binary-search program that was correct.

When I said that I didn't think binary searching was that difficult, he challenged me to write a binary-search program then and there. Having had a bit (well, more like a byte) to drink by then, I declined his offer.

He gave me some examples of how binary-search programs go wrong. The overall idea of repeatedly bisecting the range to be searched is simple enough; where trouble starts is when the range is almost narrowed down to a single element.

At that point, one has to be careful not to exclude the element being sought from the range before you have had the chance to inspect it. It is also essential never to try to look at an element outside the original array bounds, even if the value being sought is out of range.

One other problem that sometimes comes up in binary-search programs is how to compute the midpoint of the range. Typically a binary search uses two variables, which we might call low and high, to represent the beginning and end of the current range. The idea is to increase the value of low (or decrease the value of high) until either the range becomes empty or the value being sought is found.

Before shrinking the range, a binary-search algorithm computes the range's midpoint. Usually, that computation is expressed as (low+high)/2. The trouble with expressing it this way is that (low+high) might overflow.

It is far from obvious, but low+(high-low)/2 gives the same result as the infinite-precision computation of (low+high)/2, so long as low is not negative. So it is clearly better to write the midpoint computation as low+(high-low)/2.

I'm sure that this potential overflow problem is one of the troubles that my friend's friend had in mind at the Monk's Inn. That, plus the fact that it didn't occur to me until years later, suggests how subtle a problem it is, and how nasty it would be for such a problem to go undiscovered.

But what really troubles me is this: How would one test for the presence of such a problem? It would happen only as part of searching an array so large as to trigger the overflow. Would the original programmer's test cases deal with such large arrays? Or would it be enough to verify that the code works with smaller inputs?

For that matter, how do we go about writing a binary-search program at all if we wish to be confident that it works?

(to be continued)

Posted by Andrew Koenig at 12:56 PM  Permalink