templates · Binary search

Binary search on the answer

  • "Minimum speed / capacity / time such that …" or "maximum x such that …"
  • Checking one guess is easy (a greedy pass), but finding the best one directly is hard
  • If a value works, every bigger value also works (or every smaller one)

Binary search on the answer

the one rule

The invariant

The answer always stays inside [lo, hi], and feasible(x) flips exactly once: false → true when you want the smallest, true → false when you want the largest.

write it from memory

The template

smallest value that works

javajava.util.*
/** Smallest speed that finishes every pile within h hours (Koko). Shape: false…false, true…true. */static int minSpeed(int[] piles, int h) {    int lo = 1, hi = 1;    for (int p : piles) hi = Math.max(hi, p);         // the biggest pile always works    while (lo < hi) {        int mid = lo + (hi - lo) / 2;        if (canFinish(piles, h, mid)) hi = mid;       // works: try smaller, keep mid        else lo = mid + 1;                            // too slow: go faster    }    return lo;                                        // the first speed that works} /** The feasibility check: one greedy pass. This is the part you write fresh for each problem. */static boolean canFinish(int[] piles, int h, int speed) {    long hours = 0;                                   // long: up to 10⁴ piles × 10⁹ hours    for (int p : piles) hours += (p + speed - 1L) / speed; // ceil(p / speed), in long    return hours <= h;}

Two pieces: a canFinish-style check, and the lower-bound loop around it. Interviewers want to hear you say "the answer is monotonic".

fill in the blanks — only these lines change per problem

  1. line 4The answer range: the smallest possible answer and one that surely works (max pile, sum of weights…).
  2. line 7Which side to keep: works → hi = mid when you want the smallest.
  3. line 15The check for one guess. Usually a greedy pass that counts hours, days or pieces.

largest value that works

javajava.util.*
/** Largest x with x * x <= n (integer square root). Shape: true…true, false…false. */static int floorSqrt(int n) {    long lo = 0, hi = n;    while (lo < hi) {        long mid = lo + (hi - lo + 1) / 2;            // round UP, or lo = mid loops forever        if (mid * mid <= n) lo = mid;                 // works: keep it, try bigger        else hi = mid - 1;    }    return (int) lo;}

Mirror image: keep mid when it works with lo = mid, so mid must round up.

fill in the blanks — only these lines change per problem

  1. line 5When the loop does lo = mid, use lo + (hi - lo + 1) / 2.
  2. line 6Works → lo = mid when you want the largest.

complexity

What it costs

time O(n log R)
About log₂ R guesses over a range of size R (10⁹ → about 30 guesses), and each guess runs an O(n) check.
space O(1)
The check reuses the input; only a few counters.

watch out

Common bugs

  • Rounding mid down while writing lo = mid. With hi = lo + 1 it never moves, so the loop is infinite.
  • An int total inside the check. Hours or days can add up past 2³¹ − 1: use long.
  • A lo that is too big or a hi that does not surely work, so the real answer is outside the range.

use it

Practise it on

learn it properly