Pattern 5 of 27

Binary Search on Answer

Binary search over the range of possible answers when checking one candidate is easy but computing the best answer directly is not.

Cost: O(n log R) time, where R is the size of the answer range
Problems: 6

When to reach for it

The prompt asks for the minimum or maximum value that still respects a limit.
If a value works, every larger value also works, or every smaller one does.
Checking a single candidate is a simple linear scan.

How it works

Here the input array is not the thing being searched. Instead, take the smallest and largest answer that could possibly be right and ask a yes/no question of the middle one: can Koko finish at this speed, can the ship carry everything with this capacity. Because feasibility is monotonic, the candidates form a run of noes followed by a run of yeses, and binary search finds the first yes. The total cost is one feasibility check multiplied by the log of the answer range.

The template

Written for Koko Eating Bananas (write-up)

def min_eating_speed(piles, h):
    def feasible(speed):
        return sum((p + speed - 1) // speed for p in piles) <= h

    lo, hi = 1, max(piles)            # smallest and largest possible answer
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid                  # works: try smaller
        else:
            lo = mid + 1
    return lo

Open in the editor Trace it line by line

Six problems, in learning order

1.Koko Eating BananasLeetCode 875A speed works if the total hours at that speed fit within h.Medium
2.Capacity To Ship Packages Within D DaysLeetCode 1011The lower bound is the heaviest package; fill days greedily to test a capacity.Medium
3.Split Array Largest SumLeetCode 410The ship-capacity check again: can the array split into at most k parts under this sum.Hard
4.Minimize Max Distance to Gas StationLeetCode 774PremiumThe answer is a real number, so search until the range is below the required precision.Not in the curated 370 yet.Hard
5.Find the Smallest Divisor Given a ThresholdLeetCode 1283A divisor works if the sum of ceiling divisions stays within the threshold.Medium
6.Minimum Number of Days to Make m BouquetsLeetCode 1482A day works if enough runs of k adjacent bloomed flowers exist by then.Medium

What usually goes wrong

Search bounds that exclude the real answer, such as a ship capacity below the heaviest package.
A feasibility check that is not truly monotonic, which quietly returns wrong answers.
Integer division rounding down where the check needs ceiling division.