Binary Search

Binary search is the standard technique for finding a value, or a boundary, inside a sorted or "monotonic" search space in O(log n) time. The core idea is simple: keep two boundaries, lo and hi, that bracket the region where the answer could live; look at the midpoint; and use one comparison to throw away half of the remaining candidates. Because the space shrinks by a factor of two on every iteration, you reach a single remaining candidate after roughly log2(n) steps — a huge improvement over an O(n) linear scan once the input gets large.

The textbook version searches a sorted array for an exact value:

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2   # avoids overflow in other languages
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1  # not found

But the real power of the pattern shows up once you realize it doesn't need a literal sorted array at all. All it needs is a monotonic predicate: a yes/no question can_we_achieve(x) whose answer flips from false to true (or true to false) exactly once as x increases. Whenever you can phrase a problem as "find the smallest/largest x such that predicate(x) holds," you can binary search directly over the space of possible answers, even if that space is a range of integers with no array in sight. This is often called "binary search on the answer," and it's the idea behind problems like Cutting Wood (find the max saw height such that the wood produced is still at least a target amount — as the height decreases, the wood produced only increases, which is the monotonic property) and Weighted Random Selection (binary search over a prefix-sum array to find which "bucket" a random point falls into).

Recognizing a hidden binary search problem comes down to spotting one of two shapes: either the underlying data is sorted (even if rotated, or split across two arrays, or arranged in a sorted matrix), or there's a monotonic condition you can test cheaply for any candidate answer and you want the boundary where it flips. If you find yourself writing "if this works for x, it will also work for every value bigger (or smaller) than x," that's the tell.

A generic template that generalizes to boundary-finding (not just exact match) looks like this:

def find_boundary(lo, hi, predicate):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if predicate(mid):
            hi = mid          # keep mid as a candidate
        else:
            lo = mid + 1
    return lo

Note the loop condition is lo < hi here, not lo <= hi — this variant converges on a single boundary index rather than searching for an exact hit-or-miss. Mixing up lo <= hi with lo < hi, or forgetting whether the discarded half should exclude mid (mid ± 1) or keep it (mid stays in play because it might be the answer), is the single most common source of bugs in binary search code, and often causes an infinite loop when lo/hi fail to shrink on some iteration.

Complexity. Standard binary search runs in O(log n) time and O(1) space in its iterative form (a recursive form costs O(log n) additional stack space). Binary search on the answer costs O(log(range) * cost of predicate), so it's only efficient when the predicate itself is cheap.

Common pitfalls to watch for: infinite loops caused by a branch that doesn't actually shrink lo or hi; getting the first-vs-last occurrence boundary backwards (searching for the first occurrence means continuing to search left even after a match, while last occurrence means continuing to search right); rotated sorted arrays requiring an extra check at each step to determine which half (left of mid or right of mid) is the "normally sorted" half before deciding where the target could be; and computing mid as (lo + hi) // 2, which can silently overflow in fixed-width-integer languages (Python doesn't have this problem, but it's worth knowing lo + (hi - lo) // 2 is the safe idiom).

This subject walks through eight problems that exercise these ideas: finding an insertion index, finding the first and last occurrence of a duplicated value, binary searching on the answer to cut wood efficiently, searching a rotated sorted array, finding the median of two sorted arrays, searching a row-and-column sorted matrix, finding a local maximum (peak) in an unsorted array, and using prefix sums with binary search to sample from a weighted distribution.