Binary Search on the Answer

When to recognise the shape

You're given an optimisation problem of the form "find the minimum (or maximum) X such that some condition holds." Test whether the condition is monotone in X: does it hold for all X above some threshold and fail for all X below? If yes, binary-search the threshold.

This works because monotonicity gives binary search a unique boundary to find. Without monotonicity, halving doesn't help, because you don't know which half the boundary lies in.

The template

def find_min_feasible(lo, hi, feasible):
    # Find the smallest x in [lo, hi) such that feasible(x) is true.
    # Assumes feasible(hi) is true (or hi is past the maximum possible answer).
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid                                    # mid might be the answer; shrink right
        else:
            lo = mid + 1                                # mid is too small; eliminate it
    return lo

The half-open [lo, hi) convention is the most robust. lo is included; hi is excluded. The loop ends when lo == hi, and that's the answer. Any other invariant (closed, open) leaves edge cases that are the source of nearly every bug in homemade binary search.

Key rules to follow without thinking:

• hi = mid when feasible(mid): mid is a valid candidate; we keep it.
• lo = mid + 1 when not feasible: mid is invalid; eliminate it from consideration.
• Initialise hi to one past the largest possible answer, not the largest answer itself.

Worked problem 1: Koko eating bananas

"Koko has piles of bananas with sizes piles[i]. Each hour she eats at most K bananas from one pile. She must finish in at most H hours. What's the minimum K?"

The predicate: "given speed K, can Koko finish in ≤ H hours?" For each pile, the hours required are ceil(piles[i] / K). Sum across piles; check if sum ≤ H.

Monotonicity: if K = 5 works, so does K = 6 (each pile takes the same or fewer hours at higher speed). Boundary: low = 1 (eat one per hour), high = max(piles) (eat the largest pile in one hour, all others trivially).

import math

def min_eating_speed(piles, H):
    def feasible(K):
        return sum(math.ceil(p / K) for p in piles) <= H
    lo, hi = 1, max(piles) + 1                          # half-open
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Time: O(n log(max(piles))). The check is O(n); we run it O(log range) times.

Worked problem 2: Capacity to ship within D days

"Packages with weights, ship in D days at a capacity C per day, packages must ship in order. Minimum C?"

Predicate: "with capacity C, can we ship in ≤ D days?" Greedy fills each day to capacity, starts a new day when adding the next package would overflow. Count the days.

Monotonicity: higher capacity is always at least as good. Boundary: low = max(weights) (must fit the largest package), high = sum(weights) (one day, ship everything).

def ship_within_days(weights, D):
    def feasible(C):
        days, curr = 1, 0
        for w in weights:
            if curr + w > C:
                days += 1
                curr = w
            else:
                curr += w
        return days <= D
    lo, hi = max(weights), sum(weights) + 1
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Worked problem 3: Split array largest sum

"Split array into K non-empty contiguous subarrays. Minimise the maximum subarray sum."

Same shape as the shipping problem (in fact, isomorphic). Predicate: "given limit L, can we split into ≤ K subarrays each summing to ≤ L?" Greedy: walk the array, start a new subarray when the running sum would exceed L. Count subarrays.

Boundary: low = max(nums), high = sum(nums) + 1.

The same template. Once you've solved one, you've solved them all.

When the shape doesn't apply

Binary search on the answer requires a monotone predicate. If the feasibility flips multiple times across the search range, the algorithm finds some boundary but not necessarily the right one. Two failure modes:

• Predicate is non-monotone in X. No fix; use a different algorithm.
• Predicate is monotone but in the wrong direction. For "find the largest X such that feasible(X)", flip the inequalities. Same template, different boundary updates.

For the largest-X variant:

def find_max_feasible(lo, hi, feasible):
    # Find the largest x in [lo, hi) such that feasible(x). Assumes feasible(lo).
    while lo < hi - 1:
        mid = (lo + hi) // 2
        if feasible(mid):
            lo = mid                                    # mid might be the answer
        else:
            hi = mid                                    # mid is too large
    return lo

Real-valued search

Some problems search a continuous range, such as minimum-time-to-reach-X-with-fuel-constraint, where the answer is a real number. The template generalises by setting a precision tolerance: loop while hi - lo > epsilon. Common epsilon: 1e-7 or 1e-9.

def find_min_real(lo, hi, feasible, eps=1e-9):
    while hi - lo > eps:
        mid = (lo + hi) / 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid
    return lo

Complexity, reasoned

Time: O(log(range) × work_per_check). For most integer problems the range is the maximum input value or its sum, so log(range) is O(log(input)), typically ≤ 60. The check function dominates; whatever its complexity, the binary search adds only a log factor.

Memory: O(1) for the search itself, plus whatever the check needs.

Where beginners go wrong

• Mixing closed and half-open conventions. Pick one. The half-open [lo, hi) form has fewer special cases.
• Checking monotonicity by intuition only. If you're unsure, evaluate feasible at a handful of points along the range; if it flips multiple times, the technique doesn't apply.
• Setting the boundary too tight. Initialising hi = max(weights) when the answer might equal that maximum gives hi == answer and the half-open loop misses it. Use hi = max + 1.
• Off-by-one in the lo/hi update. hi = mid when feasible (mid stays as a candidate); lo = mid + 1 when not (mid is eliminated). Reversing them causes infinite loops or wrong answers.
• Trying to binary-search on a predicate of multiple variables. If the answer depends on two free parameters, you may need nested binary search (rare) or a different approach entirely.

What to read next

The Sorting & Search module covers binary search on sorted arrays, the simpler case from which this technique generalises. State Design Templates covers DP, the most common alternative when the shape isn't quite monotone. The blog essay Recognise the Shape applies the same pattern-matching reasoning to other algorithmic shapes.