Binary search is an algorithm that locates a target value in a sorted sequence by comparing it with the middle element and discarding the half that cannot contain it, repeating until the value is found or the interval is empty. In algorithms and programming, it is the standard example of a logarithmic-time method: a sorted array of one million elements needs at most 20 comparisons.
The technique applies far beyond looking up numbers in arrays. Any problem with a monotonic predicate, a yes-or-no condition that switches from false to true exactly once across an ordered range, can be solved by the same halving logic, which is why binary search appears in database indexes, version-control tools, numerical solvers and competitive programming.
How binary search narrows the interval
Binary search maintains two boundaries, usually called low and high, that enclose every position where the target could still be. Each step computes a midpoint, compares the element there with the target, and moves one boundary past the midpoint. Because each comparison removes half of the remaining candidates, the interval shrinks from n to n/2, n/4 and so on.
The loop ends in one of two ways: the middle element equals the target, or the boundaries cross and the interval becomes empty. In the second case, the final value of low is the insertion point, the position where the target would have to be inserted to keep the sequence sorted. Many library functions return this position instead of a simple not-found flag.
The following table traces a search for the value 37 in a sorted array of 16 elements, showing how quickly the candidate range collapses.
| Step | Interval (indexes) | Middle index | Decision |
|---|---|---|---|
| 1 | 0 to 15 | 7 | Middle value 29 is smaller, search right half |
| 2 | 8 to 15 | 11 | Middle value 44 is larger, search left half |
| 3 | 8 to 10 | 9 | Middle value 35 is smaller, search right half |
| 4 | 10 to 10 | 10 | Middle value 37 matches, return index 10 |
Complexity and performance of binary search
In Big O notation, binary search runs in O(log n) time in the worst and average cases and O(1) time in the best case, when the first midpoint is the target. The iterative version uses O(1) extra memory; a recursive version uses O(log n) stack space unless the compiler eliminates the tail call.
The table below shows the maximum number of comparisons for typical collection sizes, computed as the ceiling of log2(n + 1). It illustrates why the time complexity barely grows as the data grows.
| Elements (n) | Linear search, worst case | Binary search, worst case |
|---|---|---|
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
| 1,000,000,000 | 1,000,000,000 | 30 |
| 2^64 | about 1.8 × 10^19 | 64 |
Real performance also depends on memory access patterns. Early probes jump across distant parts of a large array, which causes cache misses, so for small arrays of a few dozen elements a linear scan is often faster in practice. Cache-friendly layouts such as the Eytzinger order or B-tree nodes reduce this penalty in performance-critical code.
Variants used in practice
Most practical uses of binary search are boundary searches rather than exact-match lookups. When the sequence contains duplicates, the exact-match version returns an arbitrary occurrence, so code that needs the first or last occurrence must use a lower-bound or upper-bound variant.
| Variant | Returns | Typical use |
|---|---|---|
| Exact match | Index of any equal element or not found | Membership test in a sorted list |
| Lower bound | First position with value greater than or equal to target | Range queries, first occurrence |
| Upper bound | First position with value strictly greater than target | Counting duplicates, last occurrence |
| Search on the answer | Smallest parameter satisfying a predicate | Capacity planning, optimization problems |
| Bisection on reals | Approximate root within a tolerance | Numerical equation solving |
The search on the answer pattern is especially powerful. If a question asks for the smallest buffer size, speed or capacity that satisfies a condition, and larger values always satisfy it too, the algorithm can test candidate values instead of array positions. Standard libraries expose these variants under names such as bisect_left in Python, lower_bound in C++ and Arrays.binarySearch in Java.
Binary search compared with other lookup methods
Binary search is one of several ways to find data, and the right choice depends on whether the data is sorted, how often it changes and whether range queries are needed. It pays off only when sorting has already been done or can be amortized over many lookups, because a sorting algorithm costs O(n log n).
| Method | Lookup time | Requirement | Main trade-off |
|---|---|---|---|
| Linear search | O(n) | None | Simple but slow on large data |
| Binary search | O(log n) | Sorted, random-access data | Inserts cost O(n) in an array |
| Hash table | O(1) average | Hash function | No ordering, no range queries |
| Balanced search tree | O(log n) | Tree structure | Fast inserts but more memory |
| Interpolation search | O(log log n) on uniform data | Sorted, evenly distributed keys | Degrades to O(n) on skewed data |
Binary search also requires random access. On a linked list, reaching the middle element takes linear time, which removes the advantage entirely. For data that changes frequently, a balanced tree or a skip list keeps the logarithmic lookup while allowing cheap insertions.
Common implementation mistakes
Binary search is short but notoriously easy to get wrong. Most bugs come from inconsistent boundary conventions, so the safest practice is to choose either a closed interval [low, high] or a half-open interval [low, high) and keep every update consistent with it.
- Integer overflow in the midpoint: computing
(low + high) / 2can overflow with fixed-width integers on very large arrays;low + (high - low) / 2avoids it. - Infinite loops: updating a boundary to
midinstead ofmid + 1ormid - 1can leave the interval unchanged when only two elements remain. - Off-by-one errors: mixing closed and half-open conventions returns the wrong index or skips the last element.
- Unsorted input: the algorithm silently returns wrong answers if the data is not sorted by the same comparison it uses.
- Inconsistent comparators: sorting with one ordering and searching with another, such as case-sensitive versus case-insensitive strings, breaks the invariant.
A reliable way to verify an implementation is to state the loop invariant explicitly, for example that every element before low is smaller than the target, and to test edge cases: an empty array, a single element, the target at both ends, missing values and long runs of duplicates.
Explained without jargon
Think of guessing a number between 1 and 100 when someone tells you only whether each guess is too high or too low. The smart strategy is to guess the middle every time: 50, then 25 or 75, and so on. Each answer throws away half of the remaining possibilities.
Binary search is that strategy written as a program. It only works when the items are already in order, like words in a dictionary. The reward is speed: even among a billion sorted items, about 30 guesses are always enough.
A typical use case
A development team discovers that a performance regression appeared somewhere among 1,000 commits made since the last good release. Testing each commit one by one would take days, because every test requires a full build and a benchmark run of several minutes.
Instead, the team uses a version-control bisect command, which applies binary search to the commit history. It checks out the middle commit, the developer marks it as good or bad, and the tool halves the range. After about 10 test runs, the tool identifies the single commit that introduced the slowdown. The search works because the predicate is monotonic: once the regression appears, every later commit contains it. The investigation takes under an hour instead of several days.