Binary Search on Answer — the shape behind dozens of interview problems.

Binary Search on Answer in Python

def min_capacity(weights: list[int], days: int) -> int:
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        need, cur = 1, 0
        for w in weights:
            if cur + w > mid:
                need += 1
                cur = 0
            cur += w
        if need <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo

See language-specific tabs at /languages/python/patterns and the SQL variant at /languages/sql/patterns.

Related patterns

Frequently asked questions

What is the binary search on answer pattern?

Binary Search on Answer is when a predicate is monotonic over the answer space, binary search the answer itself. Time O(log R · feasibility(n)) where R is the answer range.

When should I use binary search on answer?

Use it when: "Minimum X such that ..." or "maximum X such that ..." phrasing. Feasibility check is O(n) or better. Answer space is an integer or bounded range.

What are the most common binary search on answer bugs?

Initializing lo too low — lo must satisfy "at least one element fits". Choosing the wrong side on equality (hi = mid - 1 vs hi = mid). Confusing "smallest good" with "largest good" boundary templates.

What problems use the binary search on answer pattern?

Representative scenarios: Bandwidth Throttle — minimum capacity that ships in D days. Hiker's Ridge — minimum split size with k chunks. Deadline Bake — minimum oven temperature meeting constraint.

Is binary search on answer on the Blind 75?

Yes — Binary Search on Answer is one of the core patterns behind the Blind 75 list. See /blind-75 for the complete mapping.