Binary search on the answer

Problem

"What is the slowest eating speed that still finishes the piles in time?" "What is the smallest ship that delivers everything in five days?" Trying every candidate costs the size of the answer range times the cost of a check. But if speed s works, so does every faster speed, so the candidates split into a prefix that fails and a suffix that works. You do not need to try them all, only find the boundary between them.

Intuition

Think of a thermostat dial. You want the lowest setting that keeps the room warm. You do not need to try every notch: if a setting is warm enough, every higher one is too, so you try the middle, then the middle of the half that remains. All you need is a way to test one setting, and the knowledge that the answer to the test changes only once.

That is the whole trick, and the whole difficulty. The binary search is the same first-true loop as the previous page. The work is in choosing bounds that surely contain the answer, and writing a check that is correct and fast, often a greedy pass over the input.

The candidates are already "sorted" by pass and fail. Binary search finds the first green cell, here 4, in 4 checks rather than 11.

Mechanics

The invariant

Pick lo as the smallest answer that could possibly be right and hi as one that is certainly feasible. The invariant: every candidate below lo fails, and hi works. Then take mid; if it works, hi = mid, else lo = mid + 1. When lo == hi that candidate is the smallest that works. Maximization is the mirror: the largest candidate that works, with lo = mid and a rounded-up midpoint, or equivalently a search on the negated candidate.

Choosing the bounds

A tight range is faster, but a loose, correct one is fine because only its logarithm matters. Lower bound: the least value that could ever work (a ship must at least carry the heaviest package; a speed must be at least 1). Upper bound: a value that surely works (carry everything in one day; eat the biggest pile in an hour). Bounds that are too tight silently exclude the answer, which is the usual bug.

Writing the check

The check answers one yes-or-no question for a fixed candidate, so it is usually a greedy scan. For shipping, load packages in order and start a new day only when the next one would overflow; greedy is optimal for a fixed capacity because delaying a cut can never help. The check's cost multiplies with the search's, so the total is O(n log R), where R is the width of the answer range.

The median of two sorted arrays

The odd one out: the search is over positions, but in a space you do not see. Merge the arrays in your head and cut the result into a left half and a right half of equal size (the left one larger for an odd total). A cut that takes i elements from the first array must take half - i from the second. The cut is correct when each side's largest left element is at most the other side's smallest right element. If the first array's left element is too big, take fewer from it; if the second's is too big, take more. Search i over the shorter array, which also guarantees j stays in range.

The two red lines are one cut through the merged order. Everything blue is no larger than everything unfilled.

Worked example

Eating speed for piles [3, 6, 7, 11] within 8 hours. Each check sums the hours at speed mid, rounding each pile up:

The slowest speed that finishes in time is 4.

Ship capacity for weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] in 5 days, searching between the heaviest package and the total:

The smallest capacity that works is 15.

Median of [1, 3, 8, 9, 15] and [7, 11, 18, 19, 21, 25]. Each step proposes taking i elements from the shorter array:

The cut is valid because 9 ≤ 18 and 11 ≤ 15. There are 11 values, an odd count, so the median is the largest value on the left: 11.

Implementation

from math import ceil


def min_eating_speed(piles, hours):
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if sum(ceil(p / mid) for p in piles) <= hours:
            hi = mid
        else:
            lo = mid + 1
    return lo


def ship_within_days(weights, days):
    def days_needed(capacity):
        used, load = 1, 0
        for w in weights:
            if load + w > capacity:
                used += 1
                load = 0
            load += w
        return used

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(mid) <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo


def median_of_two(a, b):
    if len(a) > len(b):
        a, b = b, a
    half = (len(a) + len(b) + 1) // 2
    lo, hi = 0, len(a)
    while lo <= hi:
        i = (lo + hi) // 2
        j = half - i
        a_left = a[i - 1] if i else float("-inf")
        a_right = a[i] if i < len(a) else float("inf")
        b_left = b[j - 1] if j else float("-inf")
        b_right = b[j] if j < len(b) else float("inf")
        if a_left > b_right:
            hi = i - 1
        elif b_left > a_right:
            lo = i + 1
        else:
            left = max(a_left, b_left)
            if (len(a) + len(b)) % 2:
                return left
            return (left + min(a_right, b_right)) / 2

ceil(p / mid) goes through floating point; for very large piles use -(-p // mid), which stays in integers. The sentinels -inf and inf stand for "no element on that side of the cut", so the comparisons work at the ends.

Variations and edge cases

• Maximize instead of minimize. To find the largest value that works, use mid = (lo + hi + 1) // 2, then lo = mid on success and hi = mid - 1 on failure. Without rounding up, the range stops shrinking when hi == lo + 1.
• Integer square root. The answer is the largest x with x * x <= n, searched over [0, n]. Comparing squares avoids floating point.
• Real-valued answers. Loop a fixed number of times (about 60 halvings reach double precision) instead of testing lo < hi.
• Split array, largest sum. It has the same check as ship capacity with a different story: the capacity is the largest allowed piece sum and days become pieces.
• Edge cases: a single pile or package, a limit equal to the number of piles (the answer is the largest pile), a check that is not truly monotone (stop and rethink), an empty array in the median (the shorter array has zero elements, and the sentinels handle it), and total counts that are even rather than odd.

Complexity and tradeoffs

• Time: O(C log R), where C is the cost of one check and R the width of the range of answers. The ship search above took 5 checks over a range of 46 values. The median search is O(log min(m, n)).
• Space: O(1) beyond the check's own needs.
• Baseline. Trying every candidate costs C × R. A direct algorithm that builds the answer is often harder to write and not always faster.
• When it fails. The pattern requires monotone feasibility. If a larger candidate can fail where a smaller one passed, the boundary is not unique and halving can discard the answer. Test monotonicity by asking "if X works, why must X + 1 work?" and be sure you can answer it.

Problems

The home problems are the capacity and rate family (eating speed, ship capacity, split array), the integer square root, and the median of two sorted arrays. The first three share one skeleton: a bounded range, a greedy check and a first-true search.

Easy

• 69. Sqrt(x) NeetCode 250
  Search for the largest integer whose square does not exceed x, a monotone yes-then-no predicate.

Medium

• 875. Koko Eating Bananas NeetCode 150 NeetCode 250
  Faster speeds never take more hours, so binary search the smallest speed whose total hours fit within h.
• 1011. Capacity To Ship Packages Within D Days NeetCode 250
  Binary search the ship capacity, greedily loading packages in order to count the days each capacity needs.

Hard

• 4. Median of Two Sorted Arrays Grind 169 NeetCode 150 NeetCode 250
  Binary search on how many elements to take from the shorter array so the two left halves together hold exactly the smaller half of all values.
• 410. Split Array Largest Sum NeetCode 250
  Binary search on the largest allowed subarray sum, greedily counting how many pieces each candidate forces.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 287. Find the Duplicate Number Medium
• 1631. Path With Minimum Effort Medium
• 778. Swim in Rising Water Hard

Connections

The loop is the first-true search from the binary search page, with candidate answers in place of array indices. The check is often greedy, which the greedy page examines, and graph problems about the smallest worst edge use the same shape with a traversal as the check.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms: the exercise on the median of two sorted arrays, and the chapter on divide and conquer.
• Skiena, The Algorithm Design Manual: the section on binary search and bisection, including searching an answer space.
• Sedgewick and Wayne, Algorithms, section 3.1: binary search and its invariant.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.