A Note on Binary Search and Overflows

Alex Muscar

January 04, 2024

I like reading old computing books and articles. I’m know I’m biased, but “they don’t make them like they used to”. The other day I was thumbing through Dijkstra’s “A Method of Programming”.

One of my hobby horses is to look at binary search implementations, and see if they have any of the common issues—off by ones, overflow, the likes. And, as it happens, Dijkstra’s book has a chapter on binary search. I didn’t expect there to be off by one errors —the whole book is about deriving correct programs— but I was curious how he chose the midpoint.

Most textbooks use something like m ← (l+u) / 2, where l and u are pointers to the lower and upper limits of the search interval. This is OK in pseudocode since there are no overflows in math. But it doesn’t work so well in the real world where integers tend to be bounded. Long story short, this was a thing in 2006.

Let’s see what Dijkstra had to say about overflows in 1988:

Note that the correctness of our solution does not depend on whether div is rounded up or down, if rounding is necessary. We are completely at liberty, therefore, to replace the assignment to h by

h := i + (ji) div 2

a version which should possibly be preferred with a view to minimizing the chance of arithmetic overflow. Versions in which termination depends critically on rounding conventions are unfortunately not unusual in the literature.

I guess it pays to read old books after all.