Binary search on the answer

Searching a range of answers

Some problems ask for the minimum (or maximum) value that satisfies a condition: the slowest eating speed that still finishes in time, the smallest truck capacity that ships everything in 5 days. Trying every value 1, 2, 3, … works but can be slow when the range is large (up to 10⁹). Binary search can jump straight to the answer, as long as the condition behaves nicely.

Monotonic checks

Write a function ok(x) that answers "is x enough?". It is monotonic if, once it becomes true, it stays true for every bigger x: false, false, false, true, true, true. A bigger truck never makes shipping take more days, so "can ship within D days with capacity x" is monotonic. You need the first true: the lower bound from Topic 4, applied to numbers instead of a list.

The template

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi] with ok(x) True; assumes ok(hi) is True."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid          # mid works: the answer is mid or smaller
        else:
            lo = mid + 1      # mid fails: the answer is bigger
    return lo

Three decisions make it work: lo is a value that might be the answer (the smallest possible), hi is a value surely good enough, and ok(x) is monotonic. Get these right and the loop is always the same four lines.

Koko eating bananas

There are piles of bananas and h hours. Each hour Koko picks one pile and eats up to k bananas from it (if the pile has fewer, she finishes it and waits for the next hour). Find the smallest speed k that finishes all piles within h hours. A pile of p takes ceil(p / k) hours, which in integers is (p + k − 1) // k. The answer is between 1 and max(piles), because eating max(piles) per hour finishes every pile in one hour each.

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

print(min_eating_speed([3, 6, 7, 11], 8))   # Output: 4

Ship packages within D days

Packages with weights must be shipped IN ORDER, some each day, and a day's total cannot exceed the ship's capacity. Find the smallest capacity that ships everything within D days. Check a capacity greedily: fill the current day until the next package does not fit, then start a new day; count the days. The answer is at least max(weights) (the heaviest package must fit) and at most sum(weights) (everything in one day).

Integer square root

The integer square root of n is the largest x with x × x ≤ n. Here you want the LAST true, so either search for the first x with x × x > n and subtract 1, or round mid up: mid = (lo + hi + 1) // 2, then lo = mid when it works and hi = mid − 1 when it does not. Rounding up stops the loop from getting stuck when hi = lo + 1. Avoid int(n ** 0.5): floats keep only about 15–16 significant digits, so for n = 10¹⁸ − 1 it returns 1,000,000,000 instead of 999,999,999. Python's math.isqrt(n) is exact.

Allocate pages: a placement classic

Books with given page counts, in order, are split among m students; each student gets a contiguous run of books and every book goes to someone. Minimise the maximum pages any student reads. It is the shipping problem in another costume: "can every student read at most x pages?" is checked greedily and is monotonic, the range is max(pages) to sum(pages), and if there are more students than books the answer is impossible (often −1). Painter's partition and splitting an array into m parts with the smallest largest sum are the same pattern.

Common mistakes

• A check that is not monotonic, so binary search jumps past the answer. Fix: argue in one sentence why a bigger x can never make ok(x) false.
• A wrong range: lo = 0 when dividing by k (ZeroDivisionError), or hi too small so the true answer is outside. Fix: lo = smallest possible answer, hi = a value that surely works.
• Using mid = (lo + hi) // 2 with lo = mid when looking for the LAST true: infinite loop. Fix: round up, mid = (lo + hi + 1) // 2.
• Computing ceil with floats, math.ceil(p / k), which can be off for huge numbers. Fix: (p + k − 1) // k.
• Forgetting the cost: it is O(n × log(range)), not O(log n). Fix: say both parts in the interview.