Binary Search on Sorted Arrays

Suppose you must keep a list of strings in alphabetical order, and you repeatedly look items up and add new ones. A linked list is a natural first choice, but it has a cost. To add an item in the right place, you must walk through the list until you find that place, and on average that means examining about half of the items. Looking up an item costs roughly the same amount of work.

A sorted array improves the lookup side. Because the items sit in a known order, a binary search can locate an item quickly. The trouble then moves to insertion: making room for a new item in the middle of an array means shifting, on average, half of the existing items over by one position. This article is about the first half of that story, the fast lookup that sorted order makes possible, and then about a tree-shaped arrangement that also makes insertion efficient.

The routine you will meet below takes a sorted array and a target value. It returns the position in the array where the target sits, or the value -1 when the target is absent. Keep one question in mind as you read: how does the routine decide where to look next, and how does it know when to stop?

A search routine has to answer two different questions: where the target is, and whether it is there at all. The second question is easy to overlook, because a routine that only handles successful searches would look correct on most inputs. A correct routine must give a definite answer in both cases.

The key fact is that inspecting a single item can rule out a large block of positions, but only because the array is sorted. If the items increase from left to right, then comparing the target with one item tells you which side of that item the target must lie on. Everything on the far side can be discarded in one move.

Rather than repeatedly modifying the array, the routine keeps track of the range of locations that could still contain the target. Two boundary variables mark that range, a lower boundary and an upper boundary. At each step, the routine looks at the item in the middle of the range. The result of that single comparison leads to one of three outcomes: the middle item is the target, the target lies in the upper half of the range, or the target lies in the lower half of the range.

The loop runs while the lower boundary has not passed the upper boundary. Each pass inspects the middle, compares, and discards one half. The loop ends in one of two ways: either the target is found at the middle, or the range becomes empty. The source's comment on that final condition puts it plainly: when the upper boundary falls below the lower boundary, the target is known not to be in the array.

The following Python function is an illustrative version of the routine described in the source. It keeps a lower and an upper boundary, looks at the middle of the range, and returns -1 when the range becomes empty.

When an ordered collection is arranged as a binary tree with a particular ordering rule, both searching and insertion can be efficient. A binary tree built this way is called a binary sort tree, often abbreviated BST. The ideas below explain the arrangement, the guarantees it provides, and the conditions under which those guarantees turn into speed.

The source makes the efficiency argument concrete. Each step leaves about half of the remaining locations, so the number of locations left falls quickly. From a range of 1000 locations, the search narrows to about 500, then about 250, then about 125, and so on, until only one location remains after about 10 steps. The number of steps is approximately the base-2 logarithm of the number of items, so a million items need only about 20 steps.

Because the step count grows with the logarithm of the array size, a tenfold or even a thousandfold increase in items adds only a few more steps. Doubling the array adds roughly one more step, because the base-2 logarithm increases by one each time the size doubles. Linear search, which may inspect every element, grows in step with the size of the array itself.