Binary Search
Halve the search space on every comparison — a sorted array of a billion elements falls in about 30 probes.
Hands on Interactive visualization
Implementation Code
export function binarySearch(a: number[], target: number): number {
let lo = 0;
let hi = a.length - 1; // closed interval [lo, hi]
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1); // overflow-safe midpoint
if (a[mid] === target) return mid;
if (a[mid] < target) {
lo = mid + 1; // discard left half including mid
} else {
hi = mid - 1; // discard right half including mid
}
}
return -1;
}Big-O Complexity
O(1) space for the iterative form; the recursive form spends O(log n) stack. The log n probes are random-access, so each one is a potential cache miss on huge arrays.
In production When to use
Every mainstream standard library ships it: C++ std::lower_bound / upper_bound, Python's bisect module, Java's Arrays.binarySearch and Collections.binarySearch, Go's sort.Search and slices.BinarySearch, Rust's slice::binary_search.
B-tree index lookups binary-search the sorted keys within each node page to pick the child pointer — a binary search at every level of the tree, on every indexed query.
git bisect binary-searches commit history for the commit that introduced a bug: thousands of commits are narrowed to one in roughly a dozen test runs.
Optimization problems with a monotonic feasibility check — smallest capacity that ships packages in D days, rate limiting thresholds, capacity planning — are solved by binary-searching the answer space rather than an array.
Log-structured storage (LSM SSTables, sorted run files, sparse index blocks) locates keys in immutable sorted files by binary search over block offsets.
Exception-table and line-number lookups, symbol resolution in sorted symbol tables, and unwind-info lookups in language runtimes are binary searches over sorted address ranges.
Trade-offs Strengths & weaknesses
- O(log n) worst case — a billion elements in ~30 comparisons.
- O(1) extra space in the iterative form.
- The lower_bound variant finds insertion points and range boundaries, not just membership.
- Generalizes beyond arrays: any monotonic predicate over an ordered domain.
- No extra data structure to maintain — a sorted array is its own index.
- Cache-compact: a sorted array has zero per-element pointer overhead, unlike trees.
- Requires sorted input — sorting first costs O(n log n) and must be maintained.
- Insertions and deletions in a sorted array are O(n); dynamic data wants a tree instead.
- Notoriously easy to get subtly wrong: boundaries, midpoints, termination.
- Random-access probes are cache-hostile on very large arrays compared to a linear scan of small ones.
- Only answers order-based queries — a hash table beats it for pure equality lookups.
Intuition Mental model
The number-guessing game
Someone picks a number between 1 and 1000 and answers only higher or lower. Guessing the middle every time is binary search — and 10 guesses always suffice, because each answer discards half of what remains.
- Guess the exact middle of the current range — any other guess splits the range unevenly and wastes information.
- Higher discards the bottom half including your guess; lower discards the top half.
- Repeat on the surviving half: 1000 becomes 500, 250, 125... one number in 10 steps.
- The range empty without a match is proof the number was never there.
- Same instinct as a dictionary: open near the middle, decide left or right, never re-read a discarded half.
Prep Interview questions
Implement binary search without an off-by-one error. What invariant do you maintain?
Why is mid = (lo + hi) / 2 a famous bug, and what is the fix?
Search a rotated sorted array in O(log n).
Find the first and last occurrence of a duplicated key.
What does binary search look like when there is no array at all?
Watch out Common bugs
With integer division, mid can equal lo when the window has two elements; setting lo = mid then never shrinks the window. Use lo = mid + 1 (closed bounds) or bias the midpoint upward when the update is hi = mid.
In fixed-width integer languages, lo + hi overflows for arrays over a billion elements. Always write lo + (hi - lo) / 2.
Writing hi = mid when the convention needs hi = mid - 1 (or vice versa) either drops the answer from the window or re-examines mid forever. The fix is mechanical once you commit to closed or half-open bounds.
Binary search on unsorted or partially sorted data returns confidently wrong answers with no error. Comparator mismatches (sorting ascending, searching with a descending comparator) cause the same silent failure.
One screen Cheat sheet
Probe the middle of a sorted window, keep the half that can still contain the target, repeat.
- Requires sorted data — that precondition is the whole contract.
- mid = lo + (hi - lo) / 2 to dodge integer overflow.
- Commit to one bound convention: closed [lo, hi] with lo <= hi, or half-open [lo, hi) with lo < hi.
- lower_bound / upper_bound answer insertion-point and range queries, not just membership.
- Generalizes to any monotonic predicate — binary search on the answer.
- Stdlib names: std::lower_bound, bisect, Arrays.binarySearch, sort.Search, slice::binary_search.