Years ago, I was reading "Programming Pearls" and the author, Jon Bentley, said that most production implementations of binary search had bugs. I thought that was absurd! It is a simple algorithm and one of very first one taught in any suitably advanced programming class. Surely, Bentley was mistaken.
But I decided to test his premise. I was interviewing job candidates at the time and started asking them to implement binary search. And those candidates failed more time than they succeeded! These were good candidates --- most had a Masters degree --- and they couldn't write an algorithm taught in an introductory programming class!
There were lots of mistakes, but the most common was an infinite loop. The algorithm would work fine with 3 or more elements in the array, but with 2 elements, there was often a case where the loop would keep looping with 2 elements!
I've thought hard about why these experienced programmers were making this mistake. And the big conclusion I came with was that they were taught to write the algorithm with an inclusive upper bound. And, when interviewed, they repeated that and used an inclusive upper bound. And because an inclusive upper bound is harder to reason about, they made mistakes. I think we need to start teaching binary search with an exclusive upper bound.
The binary search algorithm maintains a continuous section of the array where the item might be location. At the start, the continuous section is the entire array. If A is the array and N is the number of items in the array, the item could be anywhere from A[0] to A[N-1]. And most textbooks teach binary search using two variables, the lower bound and upper bound, for that range of indices. And they use L=0 and U=N-1. The upper bound, U, is an inclusive upper bound because N-1 is a valid element.
The inclusive upper bound makes sense to a new programmer. And to inexperienced programmers in 1940's and 1950's when binary search was first published. But programmers since then have learned to denote ranges with an exclusive upper bound. That is, using U=N. It is "exclusive" because U is not a valid index into A[].
Why have programmers come to denote ranges with an inclusive lower bound (L is a valid index, if the array isn't empty) and an exclusive upper bound? Because it is easier to reason about. It has the following properties.
These are all good properties. They make code easy to write and easier to reason about. As a result, almost all code that deals with ranges now uses an inclusive lower bound and an exclusive upper bound.
When you use the exclusive upper bound, the code for binary search becomes pretty natural:
function binary_search_exclusive_upper_bound(A[], N, V):
L := 0
U := N
while U-L > 0 do
M := L + floor((U-L)/ 2)
if A[M] = V then
return M
else if V < A[M] then
U := M
else:
L := M+1
return unsuccessful
Because this code uses the exclusive upper bound, it is easier to verify the many conditions that lead to a correct implementation of binary search.
I believe code is not just about working but clearly communicating that it is correct. And using exclusive upper bounds does exactly that.
Having sat through roughly 50 interviews, I've thought a lot about binary search and I would like to propose another improvement to our teaching of it. I think the designers of Java's Arrays.binarySearch() library function got the right interface. We should teach that interface.
Designing function interfaces is hard. We need to think about all the inputs and outputs and come up with a good way to reason about the function. For binary search, the sticking point is what to return when the item we are searching for is not in the array.
We could return a "sum type". In C, that's known as a "union". In C++ and Java, that's implemented as a class with 2 derived classes of different types. But that's a complicated result.
We could also return a "sentinel", a special value with special meaning. For example, choosing the value -1, which is not a valid index.
Much simpler is what the Java designers chose: always return a valid location. The Java function returns the location where the element would be inserted into the array to keep it sorted. If the value is already in the array, the location will already hold a copy of the value!
Moreover, that design allows the binary search function to be used for more than just lookup. It can be used to insert.
And when you are thinking with that interface in mind, you actually end up with a faster loop. There is only one branch inside the loop.
function binary_search_better(A[], N, V)
L := 0
U := N
while U-L > 0 do
M := L + floor((U-L)/ 2)
if A[M] < V then
L := M+1
else:
U := M
return U
I think this is the version of binary search we should be teaching.
I believe binary search is usually taught with an inclusive upper bound because it is such an old algorithm. When it was created, we didn't have the habit (which I learned with C in the early 80's) of using an exclusive upper bound. But almost all array code now uses the exclusive upper bound. Using the exclusive upper bound is easier to reason with. I believe strongly that students would benefit substantially by using exclusive upper bounds.
Michael Nahas
former Adjunct Faculty of University of Virginia
former Instructor at Johns Hopkins Center for Talented Youth