Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Binary Search on the Answer

Editorial

Searching for an answer, not in an array

Koko has piles of bananas, [3, 6, 7, 11], and 8 hours. Each hour she picks a pile and eats up to k bananas from it (a smaller pile is finished, and the rest of that hour is wasted). What's the slowest speed k that finishes every pile within 8 hours?

There's no sorted array here. But look at the question "can she finish at speed k?" for k = 1, 2, 3, …. At those speeds she needs 27, 15, 10, 8, 8, 6 hours.

Faster never takes longer, so once a speed works, every faster speed works. The answers are no, no, no, then yes from k = 4 on: they flip once. That's the first yes from Introduction to Binary Search, over the possible answers instead of an array. This is binary search on the answer.

Binary search on the answer for Koko Eating Bananas with piles 3, 6, 7, 11 and 8 hours. The speeds 1 to 11 form a row, and under each the check: the hours she needs at that speed, and whether that fits in 8. Speeds 1 to 3 say no and 4 on say yes, so the answers flip once, and binary search finds the first yes, speed 4, in a few checks.

The recipe

Every problem in this lesson is solved in the same five steps:

  1. What are you choosing? A number: a speed, a capacity, a distance.
  2. The check. Given a candidate x, can it be done? Write it as its own function. It's usually a greedy pass over the input, O(n).
  3. Why it flips once. If x works, does every more generous x work too? Faster eating, a bigger ship, a looser limit: yes. This is the step to prove, not assume.
  4. The bounds. lo is the smallest answer that could possibly work, hi one that surely does. Loose bounds are fine: a range of a billion costs only 30 checks.
  5. The loop. The first-yes loop from Introduction to Binary Search for a minimum, its last-yes loop for a maximum.

For Koko: the speed; the check adds up ⌈pile / k⌉ hours; faster never takes longer; lo = 1, hi = max(piles) (at that speed every pile takes one hour, and the problem promises at least that many hours); the first yes.

Binary search over Koko's speeds — The row is the possible speeds. Each step checks the middle speed: green when she finishes in time, amber when she doesn't.

long long hoursAt(const vector<int>& piles, long long k) {
    long long hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;        // ceil(p / k): a pile takes whole hours
    return hours;
}

int minEatingSpeed(const vector<int>& piles, int h) {
    int lo = 1, hi = *max_element(piles.begin(), piles.end());   // speed max always works: one hour a pile
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (hoursAt(piles, mid) <= h) hi = mid;          // yes: mid is fast enough, maybe slower works too
        else lo = mid + 1;                               // no: she needs to eat faster than mid
    }
    return lo;                                           // the slowest speed that finishes in h hours
}

def hours_at(piles, k):
    return sum((p + k - 1) // k for p in piles)         # ceil(p / k): a pile takes whole hours


def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)                              # speed max always works: one hour a pile
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_at(piles, mid) <= h:
            hi = mid                                    # yes: mid is fast enough, maybe slower works too
        else:
            lo = mid + 1                                # no: she needs to eat faster than mid
    return lo                                           # the slowest speed that finishes in h hours

static long hoursAt(int[] piles, long k) {
    long hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;        // ceil(p / k): a pile takes whole hours
    return hours;
}

static int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = Arrays.stream(piles).max().getAsInt();   // speed max always works: one hour a pile
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (hoursAt(piles, mid) <= h) hi = mid;          // yes: mid is fast enough, maybe slower works too
        else lo = mid + 1;                               // no: she needs to eat faster than mid
    }
    return lo;                                           // the slowest speed that finishes in h hours
}

function hoursAt(piles, k) {
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p / k);    // a pile takes whole hours
    return hours;
}

function minEatingSpeed(piles, h) {
    let lo = 1, hi = Math.max(...piles);                 // speed max always works: one hour a pile
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (hoursAt(piles, mid) <= h) hi = mid;          // yes: mid is fast enough, maybe slower works too
        else lo = mid + 1;                               // no: she needs to eat faster than mid
    }
    return lo;                                           // the slowest speed that finishes in h hours
}

Each prints 4, 30, 23 and 1 for [3, 6, 7, 11] with h = 8, [30, 11, 23, 4, 20] with h = 5, [30, 11, 23, 4, 20] with h = 6 and [1] with h = 1. Trying every speed would take up to max(piles) checks, 11 here and a billion in the worst case; binary search takes about 30.

Minimize the maximum

Split Array Largest Sum: split [7, 2, 5, 10, 8] into 2 parts that keep their order, so that the largest part's sum is as small as possible. The thing you choose is that cap. The check: with a cap, fill parts greedily from the left and start a new part when the next number won't fit. If that needs k parts or fewer, the cap works. A bigger cap never needs more parts, so the answers flip once.

The bounds: no part can be smaller than the biggest number, and one part holding everything is the total. So lo = max(nums) and hi = sum(nums).

def parts_needed(nums, cap):
    parts, current = 1, 0
    for x in nums:
        if current + x > cap:        # x doesn't fit: start a new part with it
            parts += 1
            current = 0
        current += x
    return parts


def split_array(nums, k):
    lo, hi = max(nums), sum(nums)    # no part can be smaller than the biggest number; one part is the total
    while lo < hi:
        mid = (lo + hi) // 2
        if parts_needed(nums, mid) <= k:
            hi = mid                 # yes: a cap of mid fits in k parts, maybe a smaller cap does too
        else:
            lo = mid + 1             # no: mid is too small
    return lo

It returns 18: a cap of 18 needs 2 parts ([7, 2, 5] and [10, 8]), and 17 needs 3. The same check, with different words, solves Capacity To Ship Packages Within D Days (parts are days), Minimize Maximum Pages Allocated (parts are students) and Painter's Partition Problem (parts are painters).

Split Array Largest Sum on 7, 2, 5, 10, 8 into 2 parts. With a cap of 18, the greedy check fills 7, 2, 5 (14) and then 10, 8 (18): two parts, a yes. With a cap of 17, it fills 7, 2, 5, then 10 (8 doesn't fit), then 8: three parts, a no. So 18 is the smallest cap that works.

Maximize the minimum

Maximize Minimum Distance (the aggressive cows problem): stalls at [1, 2, 8, 4, 9], 3 cows, and you want the cows as far apart as possible, measured by the closest pair. The thing you choose is that smallest gap. The check: sort the stalls, put a cow in the first, and put the next cow in the first stall at least the gap further on. If all the cows fit, the gap works.

This flips the other way: if a gap works, every smaller gap works too. So the answers run yes, yes, …, no, and the answer is the last yes: the other loop from Introduction to Binary Search, with mid rounded up.

def can_place(stalls, cows, gap):
    placed, last = 1, stalls[0]      # the first cow goes in the first stall
    for s in stalls[1:]:
        if s - last >= gap:          # far enough from the last cow: place one here
            placed += 1
            last = s
    return placed >= cows


def max_min_distance(stalls, cows):
    stalls = sorted(stalls)
    lo, hi = 1, stalls[-1] - stalls[0]           # the answer is in [lo, hi]
    while lo < hi:
        mid = (lo + hi + 1) // 2                 # round up: the next line may set lo = mid
        if can_place(stalls, cows, mid):
            lo = mid                             # yes: a gap of mid works, maybe a bigger one does
        else:
            hi = mid - 1                         # no: mid is too big
    return lo

It returns 3: stalls 1, 4 and 8 (or 1, 4, 9) keep every cow at least 3 apart.

Answers that aren't whole numbers

Minimize Max Distance to Gas Station wants a real number, so there's no mid + 1: the range never becomes a single value. Loop a fixed number of times instead. Each step halves the range, so 100 steps shrink any range far below what a double can even tell apart. And when the answer is a whole number but the question is about a real one, like an integer square root, the last-yes loop does it exactly:

def sqrt_real(x):
    lo, hi = 0.0, max(1.0, x)        # the square root of x is in [lo, hi]
    for _ in range(100):             # 100 halvings: far below a double's precision
        mid = (lo + hi) / 2
        if mid * mid >= x:
            hi = mid
        else:
            lo = mid
    return hi


def isqrt(x):
    lo, hi = 0, x                    # the largest r with r * r <= x is in [lo, hi]
    while lo < hi:
        mid = (lo + hi + 1) // 2     # a last yes: round up
        if mid * mid <= x:
            lo = mid
        else:
            hi = mid - 1
    return lo

It prints 1.414213562 3 4 1000000000: √2 to nine places, then ⌊√15⌋ = 3, ⌊√16⌋ = 4 and ⌊√10^18⌋ = 10^9, with no floating-point rounding to worry about. Square Root of an Integer and Find nth root of m are this loop.

When to search the answer

Clues:

  • "the minimum (or maximum) value such that…", where checking one value is easy but finding it directly isn't.
  • "minimize the largest" / "maximize the smallest": almost always this pattern.
  • A limit you must stay within: hours, days, parts, a threshold.

Before you start, prove the check flips once. If it doesn't, binary search can skip right over the answer: "split into exactly k parts" is the kind of rule to rewrite as "at most k" first. And keep the check fast: binary search runs it about log(range) times, so an O(n) check gives O(n log range) in all.

Common mistakes

Rounding the hours down. p // k

On [3, 6, 7, 11] with h = 8 it returns 3, not 4. A pile of 11 at speed 3 takes 4 hours, not 3: the last hour still counts. Round up: (p + k - 1) // k.

Starting at 0. lo, hi = 0, max(piles)

On [1] with h = 1 it crashes with ZeroDivisionError: integer division or modulo by zero: the first mid is 0, and the check divides by it. The smallest possible speed is 1.

An upper bound that's too small. hi = max(nums) in Split Array Largest Sum

On [7, 2, 5, 10, 8] with k = 2 it returns 10, a cap that needs 3 parts. The answer, 18, was outside the range from the start, so no loop could find it. hi must be a value that surely works: the total.

Forgetting to sort. stalls = sorted(stalls) missing

On [1, 2, 8, 4, 9] with 3 cows it returns 1, not 3. The greedy placement walks the stalls in order of position; out of order, "far enough from the last cow" compares the wrong pairs.

Check yourself

Quiz

1 / 5

Multiple choice

Koko, piles [3, 6, 7, 11], h = 8: at speed 5 she needs 8 hours. What does the loop do?

Practice problems

From easier to harder:

  1. Square Root of an Integer: the last yes, x · x ≤ n.
  2. Find nth root of m: the same with a power.
  3. Kth Missing Positive Number: binary search on how many numbers are missing before an index.
  4. Find the Smallest Divisor Given a Threshold: Koko with a different sum.
  5. Koko Eating Bananas: the recipe.
  6. Minimum Number of Days to Make m Bouquets: the check counts bouquets of adjacent flowers.
  7. Capacity To Ship Packages Within D Days: minimize the maximum.
  8. Maximize Minimum Distance: the last yes.
  9. Minimize Maximum Pages Allocated: minimize the maximum, with students.
  10. Split Array Largest Sum: the same check.
  11. Painter's Partition Problem: the same check, with painters.
  12. Minimize Max Distance to Gas Station: a real-valued answer.

Next: Binary Search on Two Sorted Arrays and Matrices.