If you think you know everything you need to know about binary search, but have not read Netty van Gasteren and Wim Feijen’s note The Binary Search Revisited, you should.
In the FLOLAC summer school this year we plan to teach the students some basics of Hoare logic and Dijkstra’s weakest precondition calculus — a topic surprisingly little known among Taiwanese students. Binary search seems to be a topic I should cover. A precise specification will be given later, but basically the requirement is like this: given a sorted array of N
numbers and a value to search for, either locate the position where the value resides in the array, or report that the value does not present in the array, in O(log N)
time.
Given that everybody should have learned about binary search in their algorithm class, you would not expect it to be a hard programming task. Yet in his popular book Programming Pearls, Jon Bentley noted that surprisingly few professions programmers managed to implement the algorithm without bugs at their first attempt. I tried it myself and, being very careful (and having learned something about program construction already), I produced a program which I believe to be correct, but rather inelegant. I tried it on my students and they did produce code with some typical bugs. So it seems to be a good example for a class about correct program construction.
The Van Gasteren-Feijen Approach
The surprising fact that van Gasteren and Feijen pointed out was that binary search does not apply only to sorted lists! In fact, the usual practice comparing binary search to searching for a word in a dictionary is, according to van Gasteren and Feijen, a major educational blunder.
Van Gasteren and Feijen considered solving a more general problem: let M
and N
be integral numbers with M < N
, and let Φ
be a relation such that M Φ N
(where Φ
is written infix), with some additional constraints to be given later. The task is to find l
such that
M ≤ l < N ∧ l Φ (l+1)
This is the program:
{ M < N ∧ M Φ N }
l, r := M, N
{ Inv: M ≤ l < r ≤ N ∧ l Φ r, Bound: r - l }
; do l+1 ≠ r →
{ l + 2 ≤ r }
m := (l + r) / 2
; if m Φ r → l := m
[] l Φ m → r := m
fi
od
{ M ≤ l < N ∧ l Φ (l+1) }
Notice first that the loop guard l+1 ≠ r
, if satisfied, guarantees that l
and r
are not adjacent numbers, therefore assigning m := (l + r) / 2
establishes l < m < r
, and thus the bound r - l
is guaranteed to decrease. The if
statement clearly maintains the invariant, if at least one of the guards are always satisfied:
l Φ r ∧ l < m < r ⇒ l Φ m ∨ m Φ r(*)
For Φ
satisfying the condition above, at the end of the loop we will find some l
such that l Φ (l+1)
.
What relations satisfy (*)
? Examples given by van Gasteren and Feijen include:
i Φ j = a[i] ≠ a[j]
for some arraya
. Van Gasteren and Feijen suggested using this as the example when introducing binary search.i Φ j = a[i] < a[j]
,i Φ j = a[i] × a[j] ≤ 0
,i Φ j = a[i] ∨ a[j]
, etc.
Searching for a Key in a Sorted Array
To search for a key K
in an ascending-sorted array a
, it seems that we could just pick this Φ
:
i Φ j = a[i] ≤ K < a[j]
and check whether a[i] = K
after the loop. There is only one problem, however -- we are not sure we can establish the precondition a[l] ≤ K < a[r]
!
Van Gasteren and Feijen's solution is to add to imaginary elements to the two ends of the array. That is, for a possibly empty array a[0..N)
, we imagine two elements a[-1]
such that a[-1] ≤ x
and a[N]
such that x < a[N]
for all x
. I believe this is equivalent to using this Φ
:
i Φ j = (i = -1 ∨ a[i] ≤ K) ∧ (K < a[j] ∨ j = N)
which still satisfies (*)
if a
is sorted. And here is the program
{ 0 ≤ N ∧ -1 Φ N }
l, r := -1, N
{ Inv: -1 ≤ l < r ≤ N ∧ l Φ r, Bound: r - l }
; do l+1 ≠ r →
{ l + 2 ≤ r }
m := (l + r) / 2
; if a[m] ≤ K → l := m
[] K < a[m] → r := m
fi
od
{ -1 ≤ l < N ∧ l Φ (l+1) }
; if l > -1 → found := a[l] = K
[] l = -1 → found := false
fi
Do not worry about the idea "adding" elements to a
. The invariant implies that -1 < m < N
, thus a[-1]
and a[N]
are never accessed, and the array a
needs not be actually altered. They are just there to justify the correctness of the program. It also enables us to handle possibly empty arrays, while the loop body seems to be designed for the case when the range [l..r)
is non-empty.
Bentley's Program
Bentley's program for binary search in Programming Pearls can be rephrased as below:
l, r := 0, N-1 ; do l ≤ r → m := (l + r) / 2 ; if a[m] < K → l := m + 1 [] a[m] = K → found := true; break [] K < a[m] → r := m - 1 fi od ; found := false
I would like to be able to derive this program in class, since this appears to be the more popular version. Apart from the presence of break
, which I do not yet know of a easy variation of Hoare logic that helps to derive it, to relate the test a[m] < K
to l := m + 1
I will have to bring in the fact that a
is sorted in an earlier stage of the development. Thus it is harder to put it in a more general picture.
For several reasons I used to believe that Bentley's program could be preferred, for example, it seems to shrink the range more effectively, assigning l
and r
to m + 1
and m - 1
, rather than m
. On a second thought I realised that it might not be true. Variable l
can be assigned m + 1
because the possibility of a[m] = K
is covered in another case with an early exit, and r
is assigned m - 1
because this algorithm represents an array segment with an inclusive right bound, as opposed to the previous algorithm.
The two algorithms do not solve exactly the same problem. With multiple occurrences of K
in the array, Bentley's algorithm is non-deterministic about which index it returns, while the van Gasteren-Feijen algorithm, enforced by the specification, always returns the largest index. When K
does not appear in the array, van Gasteren and Feijen's program could be more efficient because it needs only one comparison in the loop, rather than two as in Bentley's case (I am assuming that the last comparison is a catch-all case and need not be implemented). What if K
does present in the array? An analysis by Timothy J. Rolfe concluded that a single-comparison approach is still preferable in average -- benefit of the early exit does not outweigh the cost of the extra comparison in the loop.
On Computing the Middle Index
There are some other interesting stories regarding the assignment m := (l + r) / 2
. Joshua Bloch from Google noted that for large arrays, adding l
and r
may cause an overflow, and Bloch was not picking on Bentley -- the bug was reported by Sun. Bloch suggests one of the following:
int m = l + ((r - l) / 2); /* for Java/C/C++ */
int m = (l + r) >>> 1; /* for Java */
m = ((unsigned int)l + (unsigned int)r)) >> 1; /* for C/C++ */
Since the publication of the blog post, there have been numerous discussions on whether it should be considered a bug in the binary search algorithm or the integer datatype, and some more machine dependent issues like whether one may have an array so large that cannot be indexed by an int
, etc.
To be more language-independent, on the other hand, Roland Backhouse in his book Program Construction: Calculating Implementations from Specifications suggested using (l + r - 1) / 2
, such that the value of m
will be ⌊(l + r)/2⌋
, regardless of whether the integral division operator actually rounds the number up or down.
Exercise?
Among the exercises suggested by van Gasteren and Feijen, this one caught my eye: let array a[0,N)
, with 0 < N
, be the concatenation of a strictly increasing and a strictly decreasing array. Use binary search to find the maximum element. (For this problem I think it is reasonable to assume that the two sub-arrays could be empty, while a
is non-empty.) This happens to a sub-routine I needed for an O(N log N)
algorithm for the maximum segment density problem (there are linear-time algorithms for this problem, though), and I do remember I started off treating it as an unimportant sub-routine but had a hard time getting it right. I am glad that now I know more about it.
References
- Roland Backhouse. Program Construction: Calculating Implementations from Specifications. John Wiley and Sons, 2003.
- Jon Bentley. Programming Pearls, Second Edition. Addison-Wesley, 2000.
- Joshua Bloch. Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Google Research Blog, June 02, 2006.
- Netty van Gasteren and Wim Feijen. The binary search revisited. AvG127/WF214, 1995.
- Timothy J. Rolfe. Analytic derivation of comparisons in binary search. SIGNUM Newsletter, Vol. 32, No. 4 (Oct 1997), pp. 15-19.
Here’s a way of doing binary search using bit operations instead of arithmetic: http://eigenjoy.com/2011/09/09/binary-search-revisited/
Java does not have unsigned types. Joshua Bloch’s proposed alternatives in Java for avoiding overflow of the middle value are either
int mid = low + ((high - low) / 2);
orint mid = (low + high) >>> 1;
.You are right. I wasn’t being clear: the
>>>
operator is available only in Java, and the last line (m = ((unsigned int)l + (unsigned int)r)) >> 1;
) is for C/C++. I’ve added some comments to clarify that. Thanks!The last name of “Netty van Gasteren” is “Van Gasteren”, not “Gasteren”.
Thanks! I’ve got to be careful next time. :)