Searching & Sorting · Searching & Sorting Fundamentals

Binary Search on Answer

Binary searching over the space of possible answers (not array indices), using a feasibility check at each candidate to decide which half of the answer range to keep.

Start free Jump to practice

5 min read
8 practice questions
5 graded problems

On this page

Description
The approach
A second flavor: maximize the minimum
Where you'll see it
Which tool for which job?
Common mistakes
Check yourself
Key takeaways
Quick revise
Practice

Description

"What's the smallest page limit that lets 3 students split these books?" "What's the slowest eating speed that finishes all piles in 8 hours?" These ask for a number, not a position in an array. Checking whether a given number works is easy, though, and if a limit works, every larger limit works too. That one-way flip is all binary search needs. Search the range of possible answers instead of an array, with a feasibility check at each guess.

We'll go from simple to more technical:

The pattern: minimize the maximum, finding the smallest value whose check passes.
A second flavor: maximize the minimum (Aggressive Cows), with the midpoint rounded up.
Where it shows up in production (capacity planning, rate limits, tuning).
What breaks it: non-monotonic checks, sloppy arithmetic, bounds, overflow.

The approach

Java

int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = max(piles);                   // the answer is in [lo, hi]: max(piles) always works
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (hoursAt(piles, mid) <= h) hi = mid;    // feasible - maybe a smaller speed also is
        else lo = mid + 1;                         // too slow - the answer is bigger
    }
    return lo;
}

long hoursAt(int[] piles, int speed) {             // the feasibility check: a greedy pass
    long hours = 0;
    for (int p : piles) hours += (p + (long) speed - 1) / speed;   // ceiling: a partial pile costs a full hour
    return hours;
}

Python

def min_eating_speed(piles: list[int], h: int) -> int:
    lo, hi = 1, max(piles)                         # the answer is in [lo, hi]: max(piles) always works
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_at(piles, mid) <= h:
            hi = mid                               # feasible - maybe a smaller speed also is
        else:
            lo = mid + 1                           # too slow - the answer is bigger
    return lo


def hours_at(piles: list[int], speed: int) -> int:   # the feasibility check: a greedy pass
    return sum((p + speed - 1) // speed for p in piles)   # ceiling: a partial pile costs a full hour

Two parts: a monotonic predicate (if speed k is enough, so is k + 1) and a feasibility check (here, total the hours at speed k). Binary search finds where the predicate flips - O(log(range)) checks of O(n) each. The check is where problems hide: using floor instead of ceiling division undercounts hours, and on piles [3, 6, 7, 11] with 8 hours it declares speed 3 enough when the answer is 4.

A second flavor: maximize the minimum

Some problems flip the other way. Placing cows in stalls to maximize the minimum gap: if a gap of d is achievable, every smaller gap is too. So search for the largest feasible d, with a greedy check that places each cow as early as the gap allows:

Java

boolean canPlace(int[] sorted, int cows, int gap) {
    int placed = 1, last = sorted[0];
    for (int i = 1; i < sorted.length; i++) {
        if (sorted[i] - last >= gap) { placed++; last = sorted[i]; }
        if (placed == cows) return true;
    }
    return false;
}
// feasible -> lo = mid (try bigger); infeasible -> hi = mid - 1; use mid = lo + (hi - lo + 1) / 2 so the range shrinks

Python

def can_place(sorted_pos: list[int], cows: int, gap: int) -> bool:
    placed, last = 1, sorted_pos[0]
    for pos in sorted_pos[1:]:
        if pos - last >= gap:
            placed += 1
            last = pos
        if placed == cows:
            return True
    return False

# feasible -> lo = mid (try bigger); infeasible -> hi = mid - 1; use mid = (lo + hi + 1) // 2 so the range shrinks

"Minimize the maximum" (Allocate Books: smallest page limit) and "maximize the minimum" (Aggressive Cows: largest gap) are the two faces of the pattern. The direction decides which half is kept - and, with lo = mid, the midpoint must round up or the loop stalls when hi = lo + 1.

Where you'll see it

Capacity planning (the smallest instance count that keeps latency under an SLO, the smallest cache that hits a target hit rate), rate-limit and batch-size tuning, and fitting a parameter to a threshold ("the largest request size that still completes in 200 ms") are binary searches over a configuration value with a measurement or simulation as the check.

Which tool for which job?

You need	Use
Smallest value that works	search for the first true, `hi = mid`
Largest value that works	search for the last true, `lo = mid` with the midpoint rounded up
A real-valued answer	a fixed number of halvings (60 to 100)
Maximum average with a length constraint	binary search the average, with a transformed check
The peak of a unimodal sequence	binary search on the sign of f(m + 1) - f(m)
A check that isn't monotonic	not binary search: scan, or rethink the check

Common mistakes

Mistake	What happens	Do this instead
A non-monotonic check	returns 13 when the first true value is 5	prove "k works implies k + 1 works" first
Floor instead of ceiling in the check	finds the boundary of the wrong predicate	`(a + b - 1) / b`
A lower bound that's too low	an impossible answer	start at the largest single item
`mid^n` in a long	cube root of 10^18 comes out as 500980407930942560	stop multiplying once past the target
`lo = mid` with the midpoint rounded down	stalls when hi = lo + 1	round up

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. What property must "is X feasible?" have for binary search on the answer to work?

Show answer

Monotonicity: it flips from false to true (or true to false) exactly once as X grows. Then the answer is the flip point, and each check tells you which side of it you're on.

2. Piles [3, 6, 7, 11], 8 hours. Why does using floor division in the hours check give the wrong answer?

Show answer

A pile of 7 at speed 3 takes 3 hours, not 2 - the last partial hour still counts. Floor division undercounts: at speed 3 it totals 8 hours (1 + 2 + 2 + 3) and accepts 3, but the real total is 10, so the answer is 4.

3. When maximizing (keep lo = mid on success), why must the midpoint round up?

Show answer

With hi = lo + 1, a rounded-down mid equals lo; if it's feasible, lo = mid changes nothing and the loop never ends. mid = lo + (hi - lo + 1) / 2 picks hi instead, so every step shrinks the range.

Key takeaways

When feasibility flips once as the candidate grows, binary search over the answer range.
Two parts: a monotonic predicate and a (usually greedy, O(n)) feasibility check.
Minimize-the-maximum keeps the left part on success; maximize-the-minimum keeps the right part (round mid up).
Get the check's arithmetic exactly right (ceilings, >= vs >), and choose bounds that contain the answer.
Guard midpoints and powers against overflow.

Quick revise

The whole skill on one page, for the night before an interview.

This page puts the lesson and the deep dive together. Skim it before practice or an interview, and go back to the full lesson for anything you don't recognize.

Pick the tool

You need	Use
Smallest that works	first true, `hi = mid`
Largest that works	last true, `lo = mid`, round up
Real answer	60-100 fixed halvings
Max average, length ≥ k	binary search the average
Unimodal peak	slope sign

Snippets worth knowing by heart

Java

long lo = maxSingle, hi = total;                      // smallest page limit that works
while (lo < hi) {
    long mid = lo + (hi - lo) / 2;
    if (feasible(mid)) hi = mid; else lo = mid + 1;
}
return lo;

Python

lo, hi = 0, n - 1                        # peak of a strictly unimodal array
while lo < hi:
    mid = (lo + hi) // 2
    if arr[mid] < arr[mid + 1]:
        lo = mid + 1
    else:
        hi = mid

The traps

A non-monotonic check: the search lands on a wrong value. Prove "k works implies k + 1 works" first.
Floor vs ceiling in the check: you find the boundary of the wrong predicate. Round up with (a + b - 1) / b.
Bounds that are too low: the search returns an impossible answer. Start at the largest single item.
Overflow in the check: mid^n in a long wraps around. Stop multiplying once you pass the target.
Rounding the midpoint with lo = mid: rounding down stalls when hi = lo + 1. Round the midpoint up.

Staff-level points, one line each

A non-monotonic check returned 13 when the answer was 5, and 13 still passes the check.
The cube root of 10^18 with plain long powers came out as 500980407930942560. Stopping early gives 1000000.
Max average with length ≥ k via binary search matched brute force on 200 arrays.
Binary search on the slope sign found the peak on 300 unimodal arrays.

Say it in an interview

"If x works, every larger x works, so I binary search the answer."
"The feasibility check is the real work. Here it's a greedy pass."
"For 'largest that works' I round the midpoint up."
"Max average becomes a non-negative-sum check after subtracting the guess."

Practice

This skill comes with 8 multiple-choice questions that tell you which misconception a wrong answer reveals and 5 graded problems. Your answers are graded and your mastery is tracked, so you'll know when the skill holds up. Running code and saving progress need a free account.

Practice Binary Search on Answer free

Find nth Root of m

MediumProCoding problemJava · Python

Given two positive integers n and m, find x such that x^n == m exactly. If no such integer x exists, return -1.