Binary Search on AnswerBinary search on the answer

01Why it exists

Reach for it when you see:The smallest feasible value, the largest feasible value, minimising the maximum, maximising the minimum, how much is enough, verifying being easier than solving.

02The core idea

Ordinary binary search looks for a position in the data; binary search on the answer looks for a value in the range of possible answers. Rewrite the question from "what is the answer" to "is x a feasible answer", and as long as feasibility is monotone in x (infeasible, infeasible, …, feasible, feasible), the answer space behaves exactly like a sorted boolean array. You can bisect it, looking for the first x that is feasible.

Three pieces are needed. First, the range of the answer, [lo, hi], which must contain the true answer and is usually the smallest possible value up to the largest: the eating speed runs from 1 to the biggest pile, the ship's capacity from the heaviest single item to the total weight. Second, the feasibility check feasible(x), which decides with a greedy pass or a simulation whether x can be done at all, typically in O(n). Third, the monotonicity: confirm that whenever x is feasible, everything more generous than x is feasible too, or the bisection has nothing to stand on.

The complexity is O(n log R), where R is the size of the answer range (hi − lo + 1). The search takes at most ⌈log₂ R⌉ rounds, and each round runs one O(n) check. A huge R (a billion) is no problem, because log₂ of a billion is only about 30. That is also why the technique suits problems whose answer is a real number or a very large integer. With a real-valued answer there is no such thing as "adjacent", so run a fixed 50 to 100 rounds instead, or keep going until hi − lo falls below your tolerance.

Get the direction straight. For the smallest feasible value (the feasible ones lie on the right), feasible(mid) means hi = mid, and otherwise lo = mid + 1 — exactly lower_bound. For the largest feasible value (the feasible ones lie on the left), success means lo = mid and failure means hi = mid - 1, and here mid must round up, (lo + hi + 1) // 2, or the loop hangs the moment lo and hi become adjacent. When the direction is not obvious, write out on paper whether the pattern reads "infeasible, infeasible, feasible, feasible" or "feasible, feasible, infeasible, infeasible".

03The algorithm

1. 1Restate the problem as a decision: "is the answer x feasible?". Confirm that the larger (or the smaller) x gets, the easier feasibility becomes — that is the monotonicity.
2. 2Fix the range lo and hi, making sure the true answer lies inside it. A wider range costs only a few more rounds (doubling it costs exactly one), but feasible has to judge every value in the range correctly: below the weight of the heaviest item, for example, loading the ship piece by piece greedily would wrongly report success, so the lower bound is set to that heaviest item.
3. 3Write feasible(x): usually a single O(n) greedy pass or simulation. It is the heart of the algorithm, so test it on its own first.
4. 4while lo < hi: mid = (lo + hi) // 2; feasible means hi = mid, infeasible means lo = mid + 1 (this is the smallest feasible value).
5. 5When the loop ends, lo is the answer. (The loop does not necessarily verify the lo it leaves behind, so when the range might hold no feasible value at all, check feasible(lo) once more.) For the largest feasible value, switch to mid = (lo + hi + 1) // 2, with lo = mid when feasible and hi = mid - 1 when not.

04Interactive demo

Koko eating bananas, with five piles and a 6-hour limit. The top row holds the candidate speeds 1 to 30, and each one that gets tried is marked feasible (green) or infeasible (amber) — the green ones always end up on the right. Below is the check itself: add up ⌈pile / k⌉ across the piles and compare it with h.

05Code

Koko's bananas and the ship's capacity both look for the smallest feasible value, with an identical skeleton and only feasible and the range swapped out. The third piece, cutting logs, looks for the largest feasible value, so note that rounding mid up and the direction of the updates are both reversed.

# Koko eating bananas (LeetCode 875): she eats k per hour; what is the slowest k that finishes within h hours?
# The answer k lies in 1..max(piles) (the problem guarantees h >= the pile count, so k = max always works)
# "k is feasible" is monotone in k: anything faster is feasible too
def min_eating_speed(piles, h):
    def feasible(k):                       # feasibility check: is speed k fast enough?
        hours = sum((p + k - 1) // k for p in piles)   # ceil(p / k) for each pile
        return hours <= h

    lo, hi = 1, max(piles)                 # the range of the answer
    while lo < hi:                         # same shape as lower_bound: find the first feasible value
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid                       # mid works, so the answer is <= mid
        else:
            lo = mid + 1                   # mid fails, so the answer is > mid
    return lo


# The same skeleton: least ship capacity (LeetCode 1011)
# Capacity cap is feasible = load in order, start a new day on overflow, and the day count is <= days
def ship_within_days(weights, days):
    def feasible(cap):
        d, cur = 1, 0
        for w in weights:
            if cur + w > cap:
                d += 1
                cur = 0
            cur += w
        return d <= days

    lo, hi = max(weights), sum(weights)    # lower bound: the heaviest item; upper bound: everything in one day
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


# Monotonicity the other way round: the largest feasible value, e.g. the longest pieces logs can be cut into (each >= L)
# Now the feasible values sit on the left, so switch to the "last feasible" form: round mid up and set lo = mid
def max_piece_length(logs, need):
    def feasible(L):                       # with pieces of length L, are there enough of them?
        return sum(x // L for x in logs) >= need

    lo, hi = 1, max(logs)
    while lo < hi:
        mid = (lo + hi + 1) // 2           # round up, or lo = mid gets stuck
        if feasible(mid):
            lo = mid                       # mid works, so the answer is >= mid
        else:
            hi = mid - 1
    return lo if feasible(lo) else 0


if __name__ == "__main__":
    print(min_eating_speed([30, 11, 23, 4, 20], 6))          # 23
    print(ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))   # 15
    print(max_piece_length([10, 7, 5], 4))                   # 5

06Practice

• LeetCode 875Koko Eating BananasMedium
• LeetCode 1011Capacity To Ship Packages Within D DaysMedium
• LeetCode 410Split Array Largest Sum (minimise the maximum)Hard
• LeetCode 1482Minimum Number of Days to Make m BouquetsMedium
• LeetCode 1552Magnetic Force Between Two Balls (maximise the minimum)Medium
• LeetCode 2226Maximum Candies Allocated to K Children (the largest feasible value)Medium