Binary Search

Binary search takes a sorted array and a target value, and returns the position where the target sits, or -1 when the target is absent. The 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 looks correct on most inputs. This article therefore follows the routine's variables step by step and keeps one question in view throughout: how does the routine decide where to look next, and how does it know when to stop?

Binary search works on a range of positions rather than on the whole array. The routine keeps track of a lower boundary and an upper boundary, and those two values mark the part of the array that could still contain the target. Each step inspects the item in the middle of that range, uses one comparison to decide which half to keep, and moves one boundary so that the discarded half falls outside the range.

A recursive version needs the same idea expressed as parameters. The original question was find this value in this array. The generalized question is find this value between these two positions of this array, inclusive at both ends. The parameters loIndex and hiIndex carry that range. The value being sought is passed along unchanged. Whole-array search is then just the special case where loIndex is 0 and hiIndex is the array length minus one, so the first call always looks like this.

Take the sorted array 3, 7, 11, 15, 19, 24, 30 at indices 0 through 6, and search for 24. The first call receives the whole range, 0 through 6. The middle position is 3, and the value there is 15. Because 24 is larger than 15, the lower half is discarded, including index 3 itself. The recursive call receives the range 4 through 6. Nothing in the array has changed; only the boundaries have moved.

The middle of the range 4 through 6 is index 5, and the value there is 24. That matches the target, so the search returns 5. The sequence of calls can be read as a stack of recursive invocations, each with its own range, and the answer flows back up from the deepest call.

Now search the same array for 10, which is not present. The search must rule out every candidate before it can conclude that the target is missing. Each row in the table below shows one call, the range it receives, the middle position it inspects, and the decision it makes.

The fourth call never computes a middle position. Its range is empty, because loIndex has moved past hiIndex, and the empty-range base case returns -1 immediately. This is the reason the empty-range check must come before any computation that depends on the range having elements. An empty range has no middle element, so trying to compute one would be meaningless.

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, 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. Each comparison therefore eliminates about half of the remaining possible positions.

The before and after view above makes the point. One comparison with the middle element 15 removed the lower four positions, leaving three candidates. Without sorting, that same comparison would say nothing about the positions it did not touch, so there would be no safe way to discard them. The discard decisions are valid only when the array increases from left to right.

Each step of binary search leaves about half of the remaining locations, so the number of candidates falls quickly. From a range of 1000 locations, the search narrows to about 500, then about 250, then about 125, and so on, until one location remains after about 10 steps. The number of steps is approximately the base-2 logarithm of the number of items, written as log2 n.

A million items need only about 20 binary search steps. A tenfold or thousandfold increase in items adds only a few more steps, because the count grows with the logarithm of the size. Linear search, which may inspect every element, grows in step with the size of the array itself. The gap between the two methods therefore widens quickly as the array grows.