Binary search

What & when

Halve a monotone search space each step: O(log n) to find a value, a boundary, or the smallest feasible answer. Reach for it when the data is sorted or a monotone predicate exists (False…False, True…True) even if the raw array isn’t, when the answer is a value in a range and you can check a guess cheaply — “binary search on the answer” (min speed, min capacity, min time) — when you need a boundary (first/last occurrence, insertion point), or when the size screams it (N ≥ 1e9, “do it in O(log n)”). Transformation: a monotone predicate reshapes the space into False…False, True…True, so one probe rules out an entire half. Complexity lever: each step halves what’s left, so O(n) candidates collapse to O(log n) probes. Part of the DSA patterns hub.

Skeleton

The first-True / lower-bound template — it subsumes exact match and answer-search.

def bisect(lo, hi):                # ← DECIDE: the search space
    # [lo, hi] = array indices, OR a range of candidate answers
    while lo < hi:                 # INVARIANT: the boundary is in [lo, hi]
        mid = (lo + hi) // 2
        if feasible(mid):          # ← DECIDE: the monotone predicate
            hi = mid               # keep mid: it might be the boundary
        else:
            lo = mid + 1           # mid fails: discard it and below
    return lo                      # smallest value with feasible(lo) True

Solving a problem = choosing the search space [lo, hi] and the monotone predicate feasible. Exact match is feasible(mid) = nums[mid] >= target over indices; answer-search sets [lo, hi] to the answer range and feasible to a “does this guess satisfy the constraint?” check.

Walkthrough

Find target 17 in a sorted array. M is the midpoint of [L, R]; each compare discards a whole half by moving L or R.

Problems

names link to my write-ups as I solve them — the list is the curriculum, the links are progress.

When it fails

• The space isn’t monotone in your predicate. Halving can throw away the answer — confirm a real False…True boundary exists, else scan or use a heap for order statistics.
• You’re after an extreme under a constraint, not a position. Binary-search the answer (smallest feasible value) and write a feasible(guess) check — that is Koko / ship-capacity.
• Duplicates blur the boundary. Decide lower- vs upper-bound explicitly, or the lo/hi updates oscillate and never settle.

Related

• Two pointers — both bound a range from two sides; binary search halves on a predicate instead of stepping one index at a time.
• Sliding window — when a feasible window length is monotone, binary-search the length and validate each guess with a window.
• heap — the alternative when there’s no monotone order to exploit but you still need the k-th or extreme element.
• In production: finding the smallest resource that meets a target is binary search on the answer — capacity / provisioning search for the least instance count, rate limit, or batch size whose feasible() satisfies the p99 / throughput SLO, plus autoscaling and max-sustainable-RPS load tests. Valid only while feasibility stays monotone in the resource.

Pattern DNA