Binary search+

Binary search works on a sorted sequence. Compare the element in the middle with the target. That single comparison tells you whether the answer is in the left half or the right half, so half of the candidates disappear at once. 100 numbers need at most 7 questions (⌈log₂100⌉), and a billion numbers need 30. Try it yourself first:

The idea is easy to state and hard to write. Most people produce an infinite loop or an off-by-one error on the first attempt. This is well documented: Jon Bentley reported in Programming Pearls that when he gave professional programmers a couple of hours to write a binary search, fewer than 10 percent produced a correct one. So do not write it from intuition. Write it from a convention.

Start by naming the interval. This chapter uses the closed interval [lo, hi]: both ends are still candidates. The invariant is that if target is in the array, its index is inside [lo, hi]. Everything already discarded has been proved not to be the answer. The loop condition and both updates follow from that one sentence:

• [lo, hi] is non-empty exactly when lo <= hi, so that is the loop condition. When lo == hi there is still one element left to check.
• If nums[mid] < target, then mid and every index to its left hold values smaller than target. The answer can only be in [mid+1, hi], so lo = mid + 1.
• If nums[mid] > target, the answer can only be in [lo, mid−1], so hi = mid - 1.

Why it terminates: mid always lies inside [lo, hi], and both updates step past mid, so each iteration removes at least the element at mid. hi − lo therefore strictly decreases and the interval reaches empty in a finite number of steps. Each iteration also removes about half of what is left, so the loop runs about log₂n times. Time O(log n). The iterative version keeps only two numbers, so extra space is O(1); written recursively, the call stack is O(log n) deep.

There is a second convention: the half-open interval [lo, hi), where hi is one position past the last candidate. Derive it the same way. [lo, hi) is non-empty when lo < hi, so the loop is while (lo < hi). Discarding the right part is hi = mid, not mid - 1, because hi is already outside the interval. Discarding the left part is still lo = mid + 1. Both conventions are correct. Mixing them is the classic bug — while (lo <= hi) together with hi = mid never ends. Pick one convention and derive the rest from it. Everything below uses the closed interval.

Here is the plain exact search (LC 704) written that way:

The exact search has a weakness. When the array contains duplicates, it returns whichever matching index it happened to land on. Many problems need the first or the last one instead. Two precise tools cover almost every such question:

• lower_bound(t) is the index of the first element ≥ t. It equals the number of elements smaller than t. If every element is smaller than t, it returns n, the array length — one position past the end.
• upper_bound(t) is the index of the first element > t. It equals the number of elements ≤ t. If every element is ≤ t, it also returns n.

Everything else follows. The number of copies of t is upper_bound(t) − lower_bound(t); if that is 0, t is absent. The first occurrence is lower_bound(t), but only after checking that this index is below n and that the value there really is t. If it is, the last occurrence is upper_bound(t) − 1.

Both are written with one template: closed interval plus a candidate variable. When the test passes, record the current mid in ans, then keep shrinking toward the side you want. The invariant is: ans is the best index found so far, and any better one is still inside [lo, hi]. Initialize ans to n so that "nothing matched" comes out correctly.

LC 34: in a sorted array, return the first and last index of target, or [−1, −1] if it is absent. Brute force: find any match, then walk left and right — that is O(n) when the array is all target, and it wastes the sorted order. Solution: the left end is lower_bound(target); the right end is the first index greater than target, minus one. Step through it:

Note the shortcut in the animation. "First index > 8" is the same position as "first index ≥ 9", so upper_bound(t) = lower_bound(t + 1). That rewrite is only valid because the values are integers, where t + 1 is the next possible value; on floating-point data you would need a real upper_bound. With integers, one lower_bound function produces both ends:

Time to correct a common belief. Binary search does not require the array to be sorted. What it requires is that one O(1) test tells you which half can be discarded. Put differently: the range must split into a part where the test is false and a part where it is true, with a single flip between them. Sorted order is the most common way to get such a split, but it is not the only way.

LC 33: a sorted array was rotated — for example [0,1,2,4,5,6,7] became [4,5,6,7,0,1,2] — and you must find target and return its index. The array is no longer sorted as a whole, so the plain search fails. The key observation: a rotation creates exactly one drop, so wherever you cut, at least one of the two halves is fully sorted. Decide which half that is, then decide whether target lies inside it, and one half can be discarded safely. LC 33 guarantees that all values are distinct, which keeps the first decision unambiguous:

The test is short: nums[lo] <= nums[mid] means [lo, mid] is sorted; otherwise [mid, hi] is. Then compare target against the two ends of that sorted half. Inside a sorted half a range comparison is reliable; the other half may contain the drop, so it is left for the next iteration.

LC 162, find a peak: return the index of any element larger than both of its neighbors. Neighboring values are never equal, and positions outside the array count as −∞. The array has no order at all, yet the direction of the slope gives the split. If nums[mid] < nums[mid+1], the values are rising at mid, and a peak must exist in [mid+1, hi]: either they keep rising all the way to hi, which is then a peak because its right neighbor is −∞, or they stop rising at some index, which is then a peak. Otherwise a peak exists in [lo, mid]. So you can halve the range by always walking uphill:

Now two dimensions. Matrix search comes in two genuinely different forms, and the difference is how far the ordering reaches:

So far the search ran over array indices. Now it runs over the answer itself. The rule is one sentence: when computing the best answer is hard but checking a candidate answer is easy, search the answer. The condition is that the check must be monotonic: there is a point where the yes/no test flips from false to true and it never flips back. Drawn out, it is a line of F…F followed by T…T. Note what is not required: the input array does not have to be sorted. Only the predicate has to be monotonic.

What you are looking for is the highlighted flip point, the first candidate that passes. That is exactly the lower_bound from §02, with one substitution: instead of comparing with target, you call a predicate you wrote yourself, usually named judge or check.

LC 875: Koko has several piles of bananas, piles, and the guards come back in h hours. Each hour she picks one pile and eats k bananas from it; if the pile runs out she waits for the next hour rather than starting another pile. Find the smallest speed k that finishes within h hours. Brute force: try k = 1, 2, 3, … and stop at the first one that works — O(max × n), and max can be 10⁹, so it is too slow. Why binary search applies: a higher speed never needs more hours, so judge(k) = Σ⌈pile/k⌉ ≤ h is monotonic in k. Search the value range [1, max(piles)] for the first k that passes. The F/T line drawn above is this exact problem, with piles = [3,6,7,11] and h = 8:

Once LC 875 is clear, the problems below are the same method in different words. Start with the standard "minimize the maximum" problem, LC 1011: packages on a conveyor belt must be loaded in their given order, and you need the smallest ship capacity that gets them all delivered within D days. judge(cap) loads packages one by one and starts a new day whenever the next one does not fit, then compares the day count with D. The lower end of the range is the heaviest package — below that, that package can never be loaded at all — and the upper end is the sum of all weights, which ships everything in one day.

The last shape is the square root (LC 69): compute ⌊√x⌋, the largest integer k with k×k ≤ x. That predicate is monotonic too, but it runs the other way: it is true for small k and false for large k, so you want the last value that passes. Record the candidate, then push right with lo = mid + 1 — the mirror image of LC 875. Keep the two directions apart: