What Is a Binary Search?

Binary search is a fast algorithm for finding a target value in a sorted collection. Instead of checking elements one by one, it repeatedly looks at the middle of the current range and discards the half that cannot contain the target. That halving gives it a time complexity of O(log n) — for a million sorted items it needs at most about twenty comparisons.

How Binary Search Works

The algorithm keeps two boundaries, low and high, that mark the range still being searched. On each step it computes the middle index, compares the value there with the target, and then:

• if the middle value equals the target, it is found;
• if the target is smaller, it moves high just below the middle, discarding the upper half;
• if the target is larger, it moves low just above the middle, discarding the lower half.

It repeats until the value is found or the range becomes empty, which means the value is not present.

A Quick Walkthrough

Suppose you are searching for 42 in the sorted list [3, 9, 18, 27, 42, 56, 71]. The middle element is 27; because 42 is larger, you discard the left half and search [42, 56, 71]. The new middle is 56; because 42 is smaller, you discard the right half and are left with [42]. One more comparison finds it — three steps instead of the five a linear scan would have needed, and that gap widens enormously as the list grows.

Time and Space Complexity

Because each comparison removes half of the remaining elements, binary search runs in O(log n) time. An iterative implementation uses O(1) extra space; a recursive one uses O(log n) space for the call stack. By comparison, a linear scan is O(n) — the advantage of binary search grows dramatically as the data set gets larger.

Requirements and Limitations

Binary search has one hard requirement: the data must be sorted on the key you are searching. It also needs fast random access to the middle element, which arrays provide but linked lists do not. If the collection changes constantly, the cost of keeping it sorted can outweigh the speedup, and a hash table (average O(1) lookups) may be a better fit for pure membership tests.

Common Pitfalls

The classic bug is computing the middle as (low + high) / 2, which can overflow on very large indices; the safe form is low + (high - low) / 2. Off-by-one errors in how the boundaries move are the other frequent source of infinite loops or missed elements, so be deliberate about whether high is inclusive or exclusive.

Binary search is a building block of efficient lookups — see how a database index uses the same divide-and-conquer idea on disk, and how memoization avoids repeating work.

Frequently Asked Questions