Binary search on the answer

How does Binary search on the answer work?

Name the smallest and largest value the answer could take. That pair is the search range.

Write a test that asks whether one candidate works. It answers only yes or no.

The test must be monotone: once it says yes, every larger candidate says yes. Without that, halving is invalid.

Take the middle candidate and run the test. Note that this is a value, not an index.

On a yes, remember it and search the smaller half. On a no, search the larger half.

The range halves every round. Thirty rounds cover a billion candidates.

1. range = 1 to 11Eating piles [3, 6, 7, 11] within 8 hours. Speed is the answer.
2. speed 6 takes 6 hoursSix hours is inside the limit. A slower speed might still fit.
3. range = 1 to 5Speed 6 is kept as the best so far. Now try the lower half.
4. speed 3 takes 10 hoursThat is over the limit. Everything below 3 is worse.
5. speed 4 takes 8 hoursIt fits exactly, and nothing smaller fits. The answer is 4.

function smallestFeasible(lo, hi, canDo) {
    while (lo < hi) {
        const mid = lo + ((hi - lo) >> 1);
        if (canDo(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// canDo(x) must be monotonic: false...false, true...true

A worked example of Binary search on the answer

Ship every package within d days

Packages must ship in the given order across d days. Pick the smallest daily capacity that still finishes in time.

A package can never be split across two days.

The answer lies between the largest single package and the sum of them all.

For one candidate capacity, fill each day greedily and count the days. Compare that count against d.

function shipWithinDays(weights, days) {
    let lo = Math.max(...weights);              // one day must hold the biggest package
    let hi = weights.reduce((a, b) => a + b, 0); // one day holds everything

    const fits = (capacity) => {
        let used = 1;
        let load = 0;

        for (const w of weights) {
            if (load + w > capacity) {
                used++;   // start a new day
                load = 0;
            }
            load += w;
        }

        return used <= days;
    };

    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (fits(mid)) hi = mid;
        else lo = mid + 1;
    }

    return lo;
}

When should you use Binary search on the answer?

These phrases in a problem statement point here:

• •minimize the maximum / maximize the minimum
• •smallest value that satisfies a condition
• •find the smallest capacity/speed/days that works
• •answer lies in a numeric range, not an array position
• •a feasibility check is monotonic (true after some point)

What is Binary search on the answer confused with?

• Binary search (array): There the range holds real stored data. Here it holds every value the answer might take.
• Greedy (exchange argument): The feasibility test is often greedy itself. The search only decides which candidate to test.
• Linear search: Trying candidates one by one is correct but slow. A monotone test lets you skip half of them.
• Dynamic programming (1-D): DP builds the answer up from smaller answers. Here the answer is guessed and then checked.

Common mistakes with Binary search on the answer

• Starting the range at zero

  The low bound should be a value that could actually work. For a capacity that is the largest item.

• A test that is not monotone

  If a larger candidate can fail after a smaller one passed, halving is wrong. Check the direction first.

• Losing the last candidate that worked

  Either store it in a variable, or move high to mid rather than past it.

• Looping forever on a decimal answer

  With real numbers lo never passes hi exactly. Run a fixed hundred rounds instead.

Which interview problems use Binary search on the answer?

• Koko eating bananas: The candidate is a speed, the test counts hours.
• Capacity to ship packages within D days: The candidate is a daily load.
• Split array largest sum: The candidate is the largest sum any part may reach.
• Minimum days to make m bouquets: The candidate is a day, the test counts finished bouquets.
• Magnetic force between two balls: Maximise the smallest gap instead of minimising a maximum.
• Find the smallest divisor given a threshold: The candidate is the divisor.
• Minimise max distance to gas station: A decimal answer, so the loop runs a fixed count.

What is the time and space complexity of Binary search on the answer?

O(n log(range))

A range of 1e9 needs about 30 tests. Total cost is O(n log range) when one test costs O(n).