Binary search is to algorithms
what a wheel is to mechanics:
It is simple, elegant, and immensely important.
— Udi Manber,
Introduction to Algorithms
Binary search is a notoriously tricky algorithm
to program correctly.
It took seventeen years after its invention
until the first correct version of binary search
was published!
— Steven Skiena, The Algorithm Design Manual
This chapter studies the following search problem: find a given number in a sorted array of numbers. More specifically, given an integer x and an increasing array v[0..n-1] of integers,
find an index m such that v[m] == x .
Some instances of this problem have no solution, of course. For example, the instances where n is 0 and those in which v[0] < x < v[1] have no solution.
Table of contents:
We begin by making a more general and more interesting formulation of the problem: find the place in the array where x should be. More precisely, given x and an increasing array v[0..n-1], find an index j such that
v[j-1] < x ≤ v[j] .
To obtain a solution to the original problem, all we need to do is compare x with v[j].
To best expoit this formulation of the problem, we allow the solution j to assume the values 0 and n. In these two cases, the expression v[j-1] < x ≤ v[j] must be interpreted with some flexibility: if j == 0, the expression reduces to x ≤ v[0] , since v[-1] is undefined; and if j == n, the expression reduces to v[n-1] < x , since v[n] is undefined. It is as if v[-1] had value −∞ and v[n] had value +∞.
In the following example, if x is 555, the solution is 4; if x is 800, the solution is 8; and if x is 1000, the solution is 13.
| 0 | n-1 | |||||||||||
| 111 | 222 | 333 | 444 | 555 | 555 | 666 | 777 | 888 | 888 | 888 | 999 | 999 |
We shall examine two algorithms for the problem: one obvious but slow and one sophisticated and much faster.
int check (int v[], int n) {
int previous = v[0], yes = 1;
for (int i = 1; i < n && yes; ++i) {
if (previous > v[i]) yes = 0;
previous = v[i]; }
return yes; }
We begin with an obvious algorithm, one that examines the elements of the array in order, one by one. Here is an implementation of the algorithm:
// This function receives an integer x and
// an increasing array v[0..n-1] and returns
// an index j in 0..n such that v[j-1] <
// x <= v[j].
int
sequentialsearch (int x, int n, int v[]) {
int j = 0;
while (j < n && v[j] < x)
++j;
return j;
}
How many iterations does the function execute? Better: how many comparisons between x and elements of v does it do? In the worst case, x is compared with each element of the array and therefore the total number of comparisons is n . Hence, if the size of the array were to be multiplied by 100, the number of comparisons would be also multiplied by 100.
The time consumption of the function is proportional to the number of comparisons that involve x, and therefore proportional to n in the worst case.
Is it possible to solve the problem in less time? Is it possible to solve the problem without comparing x with each element of the array? As we shall see, the answer is affirmative.
int seqSearch2 (int x, int n, int v[]) {
int j;
for (j = 0; j < n; ++j)
if (x <= v[j]) break;
return j; }
int seqSearch3 (int x, int n, int v[]) {
int j = 0;
while (v[j] < x && j < n) ++j;
return j; }
int seqSearch4 (int x, int n, int v[]) {
if (n == 0) return 0;
if (x > v[n-1]) return n;
return seqSearch4 (x, n-1, v); }
There is an algorithm much faster than sequential search. It is analogous to the method that one uses to find a word in a dictionary of old (the one that looks like a thick book). Of course the ideia only works because the array is sorted.
// This function receives an integer x // and an increasing array v[0..n-1] // and returns an index j in 0..n // such that v[j-1] < x <= v[j]. int binarysearch (int x, int n, int v[]) { int l = -1, r = n; // attention! while (l < r-1) { int m = (l + r)/2; if (v[m] < x) l = m; else r = m; } return r; }
Simple and clean!
The names of the variables were not chosen at random:
l stands for left
,
m stands for middle
and
r stands for right
.
The result of the division by 2 in the expression
(l+r)/2 is automatically
truncated, since the variables are of type int.
For example,
if l is 6 and r is 9,
the value of the expression
(l+r)/2 is 7.
| 0 | l | r | n-1 | |||||||||
| 111 | 222 | 333 | 444 | 555 | 555 | 666 | 777 | 888 | 888 | 888 | 999 | 999 |
The ideia of binary search is a veritable egg of Columbus! This ideia is the point of departure of several efficient algorithms to many problems.
l = -1; r = nof the function binarysearch by the three following lines. Discuss this variant of the code.
if (v[n-1] < x) return n;
if (x <= v[0]) return 0;
// now v[0] < x <= v[n-1]
l = 0; r = n-1;
while (l < r-1)is replaced by
while (l < r)? or by
while (l <= r-1)? What happens if we replace
(l + r)/2by
(l + r - 1)/2or by
(l + r + 1)/2or by
(r - l)/2? What happens if
if (v[m] < x)is replaced by
if (v[m] <= x)? What happens if
l = mis replaced by
l = m+1or by
l = m-1? What happens if
r = mis replaced by
r = m+1or by
r = m-1?
To understand the function binarysearch,
all we need
to do is check that,
at the beginning of each repetition of the while
,
immediately before
l is compared with r-1,
the relation
v[l] < x ≤ v[r]
holds. This relation is, therefore, invariant. (The algorithm was actually built around this relation!) Note the similarity between the invariant and the goal v[j-1] < x ≤ v[j] we are pursuing. The invariant holds, in particular, at the beginning of the first iteration: just pretend that v[-1] is −∞ and v[n] is +∞.
At the beginning of each iteration, by virtue of the invariant, we have v[l] < v[r] and therefore l < r, since the array is increasing. At the beginning of the last iteration, we have l >= r-1 and therefore l == r-1. The invariant relation now shows that, by returning r, the function is behaving as promised!
In each iteration we have l < m < r (why?). Hence, both r - m and m - l are strictly smaller than r - l. Therefore, the sequence of values of r - l is strictly decreasing. It is for this reason that the execution of the function terminates, sooner or later.
How many iterations the function binarysearch executes when processing an array with n elements? At the beginning of the first iteration, r - l is approximately n. At the beginning of the second, it is approximately n/2. At the beginning of the third, approximately n/4. At the beginning of the k+1-th, approximately n/2k. When k surpasses log n , the value of n/2k becomes smaller than 1 and the execution of the algorithm stops. (See the computation of log n in another chapter.) Hence, the number of iterations is approximately
log n
in the worst case as well as in the best. The approximate number of comparisons of x with elements of the array is also log n. Here are some examples when n is power of 2:
| n | 32 | 1024 | 32768 | 1048576 | 33554432 | … | |
| log n | 5 | 10 | 15 | 20 | 25 | … |
The value of log n grows very slowly since log transforms multiplications into additions. For example, if a search in an array of size n requires C comparisons, then a search in an array of size 2n will require only C+1 comparisons, a search in an array of size 8n will require only C+3 comparisons, and a search in an array of size 100n will require less than C+7 comparisons.
The time binarysearch consumes is proportional to the number of comparisons between x and elements of v. Hence, the time consumption is proportional to log n.
Implementations of binary search require care and attention to details. It is very easy to write an implementation that gives wrong answers or ends up in an infinite loop. The exercises below discuss alternative versions of binarysearch that are different from the one examined above. All strive to find x in v[0..n-1]. All would like to produce an index j in 0..n such that v[j-1] < x ≤ v[j].
l = 0; r = n;
while (l < r) { // v[l-1] < x <= v[r]
m = (l + r)/2;
if (v[m] < x) l = m+1;
else r = m;
} // l == r
return r;
l = 0; r = n-1;
while (l <= r) { // v[l-1] < x <= v[r+1]
m = (l + r)/2;
if (v[m] < x) l = m+1;
else r = m-1; } // l == r+1
return r+1;
l = -1; r = n-1;
while (l < r) {
m = (l + r)/2;
if (v[m] < x) l = m;
else r = m-1; }
return r+1;
l = -1; r = n-1;
while (l < r) {
m = (l + r + 1)/2;
if (v[m] < x) l = m;
else r = m-1; }
return r+1;
To formulate a recursive version of binary search
we must slightly generalize the problem,
changing v[0..n-1] into v[a..b].
The bridge between the basic and the generalized formulations
is a wrapper
function
binarysearch2
that outsources the job
to a recursive function bsearch.
// This function receives an increasing array
// v[0..n-1] and an integer x and returns an
// index j in 0..n such that
// v[j-1] < x <= v[j].
int
binarysearch2 (int x, int n, int v[]) {
return bsearch (x, -1, n, v);
}
// Receives an increasing array v[l+1..r-1]
// and an integer x such that v[l] < x <= v[r]
// and returns an index j in l+1..r such that
// v[j-1] < x <= v[j].
static int
bsearch (int x, int l, int r, int v[]) {
if (l == r-1) return r;
else {
int m = (l + r)/2;
if (v[m] < x)
return bsearch (x, m, r, v);
else
return bsearch (x, l, m, v);
}
}
(The keyword static is there to indicate that the function bsearch has an auxiliary nature and will not be called directly by the user of the binary search algorithm.)
What is the depth of the recursion in the function bsearch? In other words, how many times bsearch calls itself? Answer: approximately log n times.
int binarysearch3 (int x, int n, int v[]) {
if (v[n-1] < x) return n;
if (x <= v[0]) return 0;
return bsearch (x, 0, n-1, v); }
int bsearch2 (int x, int l, int r, int v[]) {
if (l > r) return r+1;
else {
int m = (l + r)/2;
if (v[m] < x)
return bsearch2 (x, m+1, r, v);
else
return bsearch2 (x, l, m-1, v); } }
<and
≤refer to the lexicographic order.