Searching a sorted array

Finding an element whose position you do not know costs a look at every element, in an array and in a linked list alike, and the only way to escape that is to know something about the order the elements are in.

What order buys

Take an array of $n$ elements held in ascending order, and compare the target $x$ with the element in the middle. Three outcomes are possible. If they are equal, the search is over. If $x$ is smaller, then because the array is sorted, $x$ cannot be anywhere in the upper half: every element there is at least as large as the middle one. If $x$ is larger, it cannot be in the lower half.

A single comparison has eliminated half the array. Nothing about the layout of memory made that possible; the ordering did. And crucially, examining the middle element is only cheap because the structure is an array, where the middle is one multiplication away. A sorted linked list gains nothing from being sorted, because reaching its middle costs $n / 2$ hops, which is the whole saving.

Both preconditions are essential and both are easy to violate silently. Binary search on unsorted data does not report an error; it returns a wrong answer, quickly.

The invariant

The algorithm keeps two indices, lo and hi, delimiting the part of the array still under consideration, and maintains one property throughout:

If $x$ is present in the array at all, its index lies in $[lo, hi]$ .

Initially $lo = 0$ and $hi = n - 1$ , and the invariant holds trivially. Each round computes $mid$ between them and compares. If $a [mid] = x$ , return. If $a [mid] < x$ , then no index at or below mid can hold $x$ , so setting $lo = mid + 1$ preserves the invariant. If $a [mid] > x$ , setting $hi = mid - 1$ preserves it. When $lo > hi$ the interval is empty, and the invariant then says $x$ is not present, which is the correct return.

Termination is separate from correctness and needs its own argument. The interval width $hi - lo + 1$ strictly decreases on every round, because mid lies within the interval and each branch excludes mid itself. A strictly decreasing non-negative integer cannot decrease forever, so the loop ends. Any implementation that lets the width stay the same on some round loops forever, and that is not hypothetical: it is the second of the two classic bugs below.

Example. Trace a binary search for 41 in the array 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, which has 15 elements at indices 0 to 14.

Round 1: $lo = 0$ , $hi = 14$ , $mid = 7$ , $a [7] = 19 < 41$ , so $lo = 8$ . Round 2: $lo = 8$ , $hi = 14$ , $mid = 11$ , $a [11] = 37 < 41$ , so $lo = 12$ . Round 3: $lo = 12$ , $hi = 14$ , $mid = 13$ , $a [13] = 43 > 41$ , so $hi = 12$ . Round 4: $lo = 12$ , $hi = 12$ , $mid = 12$ , $a [12] = 41$ , found.

Four comparisons, against an expected eight for a linear scan of a 15-element array.

Now you. Trace the same search for 13 in the same array. How many comparisons?

Answer

Round 1: $lo = 0$ , $hi = 14$ , $mid = 7$ , $a [7] = 19 > 13$ , so $hi = 6$ . Round 2: $lo = 0$ , $hi = 6$ , $mid = 3$ , $a [3] = 7 < 13$ , so $lo = 4$ . Round 3: $lo = 4$ , $hi = 6$ , $mid = 5$ , $a [5] = 13$ , found.

Three comparisons. Note that the count depends on where the element sits, not only on $n$ : the maximum for 15 elements is four.

Counting it exactly

Each round at worst halves the interval, so after $k$ rounds the interval holds at most $n / 2^{k}$ elements. The search finishes when that falls below one, which happens at $k = ⌊ \log_{2} n ⌋ + 1$ , equivalently $⌈ \log_{2} (n + 1) ⌉$ . The two expressions agree for every positive $n$ , and either is the exact worst-case number of comparisons.

The numbers are what make the point.

$n$	worst-case comparisons
15	4
1000	10
$10^{6}$	20
$10^{9}$	30
$10^{12}$	40

Twenty comparisons to search a million items; thirty for a billion. Each doubling of the data adds exactly one comparison, which is what logarithmic cost means in practice and why it is treated as effectively free. A linear scan of the same billion items averages 500 million comparisons.

Note that the sorted array is not free. Keeping it sorted under insertions costs $Θ (n)$ per insertion, because a new element has to be placed in order and everything after it shifted. Binary search is therefore the right structure for data that is read far more often than written: a lookup table, a static index, a sorted array of identifiers rebuilt in a batch.

Example. You have a million records and need to perform $k$ lookups. Linear search averages $n / 2$ comparisons each. Sorting first costs about $n \log_{2} n$ comparisons, after which each lookup costs 20. Above what $k$ is sorting worth it?

Linear costs $500 {,} 000 k$ . Sorting plus searching costs $10^{6} \times 19.93 + 20 k = 1.993 \times 10^{7} + 20 k$ . Setting them equal: $499 {,} 980 k = 1.993 \times 10^{7}$ , so $k \approx 40$ . Above about forty lookups, sorting pays for itself; below it, scanning is cheaper. The answer is far smaller than most people guess, which is the practical lesson.

Now you. Same numbers, but the data changes constantly, so the array must be re-sorted after every lookup. Now which wins?

Answer

Sorting once per lookup costs about $1.993 \times 10^{7} + 20$ comparisons per lookup, against 500,000 for a linear scan: sorting loses by a factor of about 40. The break-even calculation only works when the sort is amortised over many searches, which is the same reason a sorted array is a poor structure for write-heavy data. That gap is what binary search trees and hash tables exist to close.

Nobody can do better, and here is why

Twenty comparisons for a million elements is impressive, but impressive is not a proof. The stronger claim is that no algorithm restricted to comparing the target against elements can do better, and it can be proved with an argument that recurs several times later in this course.

Model any such algorithm as a decision tree. Each internal node is a comparison the algorithm might make, each edge is an outcome, and each leaf is an answer the algorithm can produce. Running the algorithm on a particular input traces one root-to-leaf path, and the number of comparisons made is that path's length. The worst-case comparison count is therefore the height of the tree.

Now count the leaves that must exist. The algorithm has to be able to answer "the target is at index 0", "at index 1", up to "at index $n - 1$ ", and "not present": at least $n + 1$ distinct answers. Distinct answers need distinct leaves, since the algorithm has learned nothing to separate them otherwise.

A binary tree of height $h$ has at most $2^{h}$ leaves. So $2^{h} \geq n + 1$ , giving

h \geq \log_{2} (n + 1)

and since $h$ is an integer, $h \geq ⌈ \log_{2} (n + 1) ⌉$ . That is exactly what binary search achieves, so binary search is optimal, not merely good.

Be precise about what has been ruled out. The bound applies to algorithms whose only access to the data is comparing elements. It does not forbid an algorithm that looks at the value of the key and computes where it should be. Interpolation search does exactly that, guessing the position by linear interpolation between the endpoints, and on uniformly distributed data it costs about $\log_{2} \log_{2} n$ comparisons: roughly 4.3 for a million items instead of 20. Its worst case, on badly skewed data such as exponentially spaced keys, degrades to $Θ (n)$ , which is why it is rarely the default. The same loophole, exploited harder, is what makes hash tables constant time, and it is the subject of a later lesson.

The two bugs everyone writes

Binary search is six lines long and notoriously difficult to write correctly. Jon Bentley reported that when he set it as an exercise to professional programmers, about ninety per cent of the submissions were wrong, and Knuth notes that although the method was published in 1946, the first correct published version of the general case did not appear until 1962.

The overflow. The natural way to compute the midpoint is $mid = (lo + hi) / 2$ . If indices are 32-bit signed integers and the array is large, the sum overflows before the division. With $lo$ and $hi$ near $2^{31} - 1 = 2 {,} 147 {,} 483 {,} 647$ , their sum is about $4.29 \times 10^{9}$ , which wraps to a negative number, and the subsequent index is out of bounds. This is not a textbook worry: it sat in the JDK's Arrays.binarySearch from version 1.2 until Joshua Bloch found and reported it in 2006, nine years, in code that had been read by thousands of people. The fix is to compute $mid = lo + (hi - lo) / 2$ , which is algebraically identical and never forms the large sum.

The non-shrinking interval. Write the loop as while (lo < hi) with the update $hi = mid$ rather than $mid - 1$ , which is the shape used for finding a boundary rather than an exact match. When $hi = lo + 1$ , the floor division gives $mid = lo$ , and if the branch taken sets $lo = mid$ , the interval does not shrink and the loop runs forever. The rule that prevents it is the termination argument above: check that every branch strictly reduces $hi - lo$ . Where the update is $lo = mid$ , the midpoint must round up instead, $mid = lo + ⌈ (hi - lo) / 2 ⌉$ .

Searching for a boundary

Exact-match search is the least useful of the binary search family, and the variants matter more in practice. The two standard ones answer "where does $x$ belong?" rather than "is $x$ here?".

Lower bound returns the index of the first element not less than $x$ : the position of $x$ 's first occurrence if it is present, and the insertion point if it is not. Upper bound returns the index of the first element strictly greater than $x$ . The difference between them is the number of copies of $x$ in the array, computed in $2 ⌈ \log_{2} (n + 1) ⌉$ comparisons without examining the duplicates at all.

These are what libraries actually expose: std::lower_bound and std::upper_bound in C++, bisect_left and bisect_right in Python. They answer range queries ("how many values lie between 100 and 200?") and they never need a separate "not found" convention, since a position is always meaningful. They are also the reason binary search generalises past arrays: any monotone predicate over an ordered domain can be bisected, which is how you find the smallest capacity that satisfies a constraint, or the first commit that broke a build. That last one is git bisect, and it finds the culprit among a thousand commits in ten builds.

Example. In the array 2, 4, 4, 4, 7, 9, what do lower bound and upper bound return for $x = 4$ , and what does the pair tell you?

Lower bound returns 1, the first index whose element is not less than 4. Upper bound returns 4, the first index whose element exceeds 4. The difference $4 - 1 = 3$ is the number of 4s in the array.

Now you. In the same array, what do lower bound and upper bound return for $x = 5$ , and what does that say?

Answer

Lower bound returns 4, the index of 7, the first element not less than 5. Upper bound also returns 4, since 7 is also the first element strictly greater than 5. The difference is 0, so 5 does not occur, and index 4 is where it would be inserted to keep the array sorted.

Every result in this lesson rests on a precondition that nothing in the course can yet supply: the array must already be in order. Producing that order is a problem in its own right, and the obvious methods for it turn out to cost quadratically, which is the subject of the next lesson.