Binary search
Search the answer, not the array: halve a monotone predicate until one candidate is left.
When it applies
Binary search applies whenever a yes/no test is monotone: once it turns true it stays true. That covers the obvious case of a sorted array, and the less obvious one where the answer is a number and checking a candidate is cheaper than constructing it.
Signals: "minimum capacity", "smallest k such that", "maximise the minimum", "first index where". Write the check first, prove it is monotone, then search.
The template
Write this from memory. Every problem in this section is a specialisation of it, and most bugs come from deviating without a reason.
lo, hi = low_bound, high_bound
while lo < hi: # invariant: the answer is in [lo, hi]
mid = (lo + hi) // 2
if feasible(mid):
hi = mid # mid might be the answer; keep it
else:
lo = mid + 1 # mid is too small
return lolong long lo = lowBound, hi = highBound;
while (lo < hi) {
long long mid = lo + (hi - lo) / 2; // no overflow
if (feasible(mid)) hi = mid; else lo = mid + 1;
}
return lo;long lo = lowBound, hi = highBound;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (feasible(mid)) hi = mid; else lo = mid + 1;
}
return lo;let lo = lowBound, hi = highBound;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (feasible(mid)) hi = mid; else lo = mid + 1;
}
return lo;let (mut lo, mut hi) = (low_bound, high_bound);
while lo < hi {
let mid = lo + (hi - lo) / 2;
if feasible(mid) { hi = mid } else { lo = mid + 1 }
}
losearch lo hi
| lo >= hi = lo
| feasible mid = search lo mid
| otherwise = search (mid + 1) hi
where mid = lo + (hi - lo) `div` 2Problems
Find a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Easy10 minInteger square root without a library
Search the candidates 0 to n for the last x with x² ≤ n, and keep the square from overflowing.
Open the problem → Easy10 minThe top of a mountain array
Nothing is sorted, but "is the next element smaller?" is false up the slope and true down it. Find the first true.
Open the problem → Easy10 minWhere a value belongs in a sorted array
Return the first position whose element is at least the target: the lower bound, which answers both "is it here" and "where would it go".
Open the problem → Easy10 minComplete rows of a coin staircase
Row k needs k coins, so k complete rows need k(k + 1)/2. Search for the last k that fits, with 64-bit arithmetic.
Open the problem → Medium15 minMinimum of a rotated sorted array
The input is not sorted, so the usual comparison is useless. Compare against the right end instead.
Open the problem → Medium15 minSearch a matrix sorted in reading order
Read row by row, the matrix is one sorted list of m × n values. Search indices 0 to mn − 1 and turn each into a row and a column.
Open the problem → Medium20 minSmallest ship that clears the backlog in D days
When the answer is a number and "is X enough?" is easy to check, search over answers rather than over data.
Open the problem → Medium25 minSpread m items to maximise the closest pair
Guess a spacing d; place items greedily, each at the first position at least d past the last. If m fit, a wider spacing might too. Search the last d that fits.
Open the problem → Medium25 minThe k-th smallest value in a sorted matrix
Search over values, not positions: count the cells ≤ x with a staircase walk in O(n), and find the smallest x whose count reaches k.
Open the problem → Medium15 minFirst and last position of a value
Two lower-bound searches, one for "at least target" and one for "greater than target", give both ends of the run.
Open the problem → Medium15 minThe one value without a partner
Before the single value, pairs start at even indices; after it, at odd ones. That switch is what the search finds.
Open the problem → Medium20 minFind a value in a rotated sorted array
Split any range at its middle and one side is in order. Test whether the target lies in that side; if not, it lies in the other.
Open the problem → Medium20 minSearch a matrix sorted along rows and columns
From the top-right corner, one comparison rules out a whole row or a whole column. m + n steps, and why plain binary search does worse.
Open the problem → Medium20 minThe largest equal share for k people
A pile of p cut into shares of x yields ⌊p / x⌋ shares. Bigger shares mean fewer of them: search for the last x that still gives k.
Open the problem → Medium20 minThe slowest rate that clears every queue in time
At rate k a queue of p items takes ⌈p / k⌉ hours. The total only falls as k rises, so search for the smallest k that fits the deadline.
Open the problem → Medium20 minCount the partners that clear a threshold
Sort one list once; each query then becomes one lower-bound search for the smallest partner that is good enough.
Open the problem → Medium20 minSearch a rotated array with repeated values
When the two ends and the middle are equal, no comparison can say which half is sorted. Shrink both ends by one and carry on.
Open the problem → Medium20 minThe first day enough adjacent flowers are open
Fix a day and count how many runs of k open flowers it gives, greedily. More days never close a flower, so search the first day that gives m runs.
Open the problem → Medium15 minResearch impact from sorted citation counts
The test compares each count with how many papers lie to its right; that test is monotone, so a lower bound finds the h-index.
Open the problem → Medium20 minEarliest time a fleet completes its trips
By time t a vehicle with round-trip time x has finished ⌊t / x⌋ trips. The fleet total never falls as t grows: search the first t that reaches the target.
Open the problem → Medium25 minLeast time for a workshop to repair every car
A mechanic of rank r needs r·n² minutes for n cars, so in t minutes they manage ⌊√(t / r)⌋. Sum over mechanics and search the first t that covers every car.
Open the problem → Hard25 minThe k-th smallest of two sorted arrays
Compare the k/2-th element of each array; the smaller one and everything before it cannot be the answer. Drop them and repeat.
Open the problem → Hard25 minThe k-th smallest entry of a multiplication table
Row i of the table holds i, 2i, …, ni, so it has min(⌊x / i⌋, n) entries ≤ x. Count in O(m) and search for the first value whose count reaches k.
Open the problem → Hard30 minMedian of two sorted arrays
Choose how many elements the left half takes from the shorter array; the rest come from the longer one. One comparison says whether to take more or fewer.
Open the problem → Hard25 minFind a value in a mountain array
Find the peak, then search the rising side in ascending order and the falling side in descending order. Left side first, for the smallest index.
Open the problem → Hard30 minLongest time n machines can run on shared batteries
Can all n machines run for t minutes? A battery can contribute at most t of its charge, so the test is Σ min(b, t) ≥ n·t. Search the last t that passes.
Open the problem → Hard30 minThe k-th smallest distance between two values
There are n²/2 distances, too many to sort. Sort the values, count pairs within distance d by sliding window, and search for the first d whose count reaches k.
Open the problem → Hard30 minSplit an array to minimise the largest part
Guess the largest allowed sum, check greedily whether k parts suffice, and binary search the guess.
Open the problem →Or sit a timed interview: a fixed window, limited submissions, and a report at the end.