Plain binary search is the familiar tool — find a value in a sorted array. But many efficiency problems ask for an answer that no array contains: the minimum speed, the maximum gap, the smallest time. Direct search has nothing to traverse. What you can usually decide is whether a given candidate x works, and that decision is monotone. When monotonicity holds, you binary-search the answer itself. That is parametric search.

Parametric search needs two ingredients. A decision function can(x) takes a candidate answer x and returns whether the problem is solvable with it. And can is monotone: as x moves in one direction, the result eventually stays True (or stays False) and never flips back. Under those two conditions the candidate space splits into a feasible region and an infeasible one, and the boundary between them is the answer.

block-beta
    columns 8
    a1["x = lo"]
    a2[" "]
    a3[" "]
    a4["x*"]
    a5[" "]
    a6[" "]
    a7[" "]
    a8["x = hi"]

    style a1 fill:#FFCDD2
    style a2 fill:#FFCDD2
    style a3 fill:#FFCDD2
    style a4 fill:#C8E6C9
    style a5 fill:#C8E6C9
    style a6 fill:#C8E6C9
    style a7 fill:#C8E6C9
    style a8 fill:#C8E6C9

The red region is can(x) == False, the green region is can(x) == True. We want x*, the first value where can flips to True. We can’t compute that boundary directly, but binary search closes in on it. Where plain binary search finds a value in a sorted array, parametric search finds the boundary of a monotone predicate.

Decisions Before the Code

Four choices come before any code. Settle them and the loop almost writes itself.

  • Direction of monotonicity — does the problem get easier or harder as x grows? This decides whether the answer is the minimum of the feasible region or the maximum.
  • The decision function — the body of can(x) -> bool. The faster and cleaner it is, the cleaner the whole solution reads.
  • lo and hi — the range where the answer can live. Each gets a one-line justification.
  • Shrink direction — when can(mid) is True, do you cut hi or grow lo? For the minimum, cut hi. For the maximum, grow lo.
flowchart TD
    A[Answer not in any array] --> B{Does the problem
get easier with x?}
    B -->|Yes| C["Define can(x)"]
    B -->|No| Z[Different approach]
    C --> D["Justify lo and hi"]
    D --> E["Shrink direction
(find_min vs find_max)"]
    E --> F[Binary search]

Example — Eating Piles in Time

The setup is plain. You are given a list piles and a deadline h. Each hour you can eat at most k from one pile; if a pile is smaller than k, you finish it and the remainder of the hour is gone. Find the smallest integer k that lets you finish every pile within h hours (LeetCode 875).

Trying every k from 1 upward runs out of time once max(piles) is large. But k is monotone: a bigger k finishes in less time, never more. Split the decision function from the binary-search shell and the structure becomes legible.

def can_eat_in_time(piles, k, h):
    return sum((p + k - 1) // k for p in piles) <= h


def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)
    answer = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_eat_in_time(piles, mid, h):
            answer = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return answer

lo = 1 because zero would mean never finishing. hi = max(piles) because you can’t eat more than one pile per hour, so any k above the biggest pile gives the same total time. The trick (p + k - 1) // k equals math.ceil(p / k): adding k - 1 before the floor pushes non-multiples up by one. Integer math only, no float precision and no conversion cost.

Justifying lo and hi

lo and hi define the candidate range. Pick them too tight and you miss the answer; pick them too loose and you waste log steps. A handful of patterns cover most cases.

  • Eating piles in time: lo = 1, hi = max(piles) — at most one pile per hour
  • Shipping capacity: lo = max(weights), hi = sum(weights) — anything below the biggest package is impossible; the sum finishes in one day
  • Routers / minimum distance between balls: lo = 1, hi = max(positions) - min(positions) — the endpoints are the physical upper bound
  • Immigration queue: lo = 1, hi = max(times) * n — the slowest officer alone clears everyone

Tightening hi with averages is tempting but risky. Floor truncation can push the true answer just outside the range. Under interview pressure, take the safe upper bound first; tighten only if time allows.

Mapping Inequalities

A single character in can(x) flips the whole answer. Map the problem statement’s wording to operators carefully.

StatementOperator
at least>=
at most<=
more than>
less than<

Right after writing can(x), trace it on a tiny input. piles = [3, 6, 7, 11], h = 8 is enough. Check can(piles, 4, 8) == True and can(piles, 3, 8) == False. A misplaced inequality surfaces immediately.

When the answer isn’t sitting in any array, binary-searching the answer itself usually works. Fix the direction of monotonicity, define can(x), give lo and hi a one-line justification each. Once those three are decided, the binary-search shell follows. The reach of parametric search is wider than it first looks. How many to eat per hour, how much to ship per truck, the minimum distance between two placements — once you stop hunting for the answer and start asking whether a candidate works, these all collapse into the same shell.