Binary Search

Halve a sorted search space each step. O(log n) lookups — and a template for searching on any monotonic condition.

Level: intermediate

What is it?

Binary search finds a target in a sorted array by comparing it with the middle element and discarding the half that cannot contain it, repeating until the target is found or the range is empty. It needs random access and sorted data. The same idea — halve the range using a yes/no test — also finds the smallest value that satisfies a monotonic condition ('binary search on the answer').

Why does it matter?

Searching a billion sorted items takes about 30 steps. Nearly every index, from B-trees to sorted files, applies this halving idea, and it is famously easy to get subtly wrong, so it is a staple of interviews.

Mental model

Guessing a number between 1 and 100 with 'higher' or 'lower' feedback. Guess 50; if it is higher, the answer is in 51–100. Each guess throws out half the remaining numbers, so seven guesses are enough.

How it works

Precondition: the data is sorted (or the predicate is monotonic: false, false, …, true, true).
Keep an invariant: if the target exists, it lies within [lo, hi]. Every step must shrink the range.
Use mid = lo + (hi - lo) // 2 to avoid overflow in fixed-width integers.
Off-by-one is the bug: decide whether hi is inclusive or exclusive and stay consistent.
Use bisect_left and bisect_right (Python) or Arrays.binarySearch (Java) instead of hand-rolling.
Binary search on the answer: find the minimum capacity, speed, or time for which a feasibility check passes.

Steps

Set lo and hi to the ends
Look at the middle element
Target smaller: keep the left half
Target larger: keep the right half
Stop when found or the range is empty

Code example: Binary search with a clear invariant

def binary_search(xs, target):
    lo, hi = 0, len(xs) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2      # avoids overflow in fixed-width languages
        if xs[mid] == target:
            return mid
        if xs[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9], 7))   # 3

Complexity and trade-offs

Time: O(log n)

Space: O(1) iterative, O(log n) recursive

Trade-offs

Enormous speed-up over linear search, but the data must be kept sorted
Requires random access; on a linked list it degrades to O(n)

Real-world usage

Lookups in sorted arrays, files, and index pages
Finding insertion points (bisect) and ranges
Optimization: minimum feasible value for a monotonic check

Common mistakes

Applying it to unsorted data.
Infinite loops from lo = mid instead of mid + 1.
Integer overflow in (lo + hi) / 2 in fixed-width languages.

Interview questions

What is the time complexity of binary search and why?

O(log n): each step discards half of the remaining range, so after k steps n / 2ᵏ items remain, and the range is empty after about log₂ n steps.

How do you binary search for the first position where a condition becomes true?

Keep lo and hi around the boundary; if the predicate at mid is true, move hi to mid (the answer may be mid), otherwise move lo to mid + 1. When lo == hi, that index is the first true.

Why is (lo + hi) // 2 a bug in some languages?

With fixed-width integers lo + hi can overflow when both are large. lo + (hi - lo) // 2 stays in range.