Binary search

Which of 1,024 versions broke it?

A merchant reports that payouts to co-operative bank accounts have been failing for weeks. Nobody knows since when. The rules file that approves these payouts has 1,024 saved versions from the quarter. Version 1 is known to be fine. Version 1,024, today's, is broken.

Checking one version means loading it into a test environment and replaying a test payout, which takes four minutes. If you start at version 2 and work upward, and the bad change is near the end, that is 1,022 checks, over 68 hours.

One fact changes the calculation. Once a change broke these payouts, every later version still contains it. So the versions run fine, fine, fine, and then broken all the way to today. Load version 512 first. The test payout fails.

Pause and predict Version 512 is broken. What does that tell you about the first broken version?

Find where false turns into true

Set aside the usual description, "look in the middle, then go left or right", and start from what the loop is looking for: a boundary.

Take a sorted array and ask a yes/no question at every index, such as "is nums[i] at least 8?". Because the array is sorted, the answers run false, false, ..., and then true to the end. The question is monotone: its answer flips once and never flips back. Binary search finds the index where it flips, the first true.

Each of the loop's moves is needed exactly as written.

Pause and predict You search [1, 3, 3, 5, 8, 8, 9, 12] for the first value that is at least 8, but when mid is true the code sets hi = mid - 1 instead of hi = mid. Where does the search end?

One loop for every boundary question

To find a value, search for the first index where "at least the target" is true, then check whether that index holds the target. The other questions you can ask of a sorted array use the same loop with a different yes/no question, which is called the predicate.

Pause and predict Take the same array. The loop can only find the first index where a question is true. How do you find the last index whose value is at most 8?

Search the range of answers

In Koko Eating Bananas, Koko eats piles of bananas at a fixed speed of k bananas an hour, one pile at a time, and has h hours. What is the slowest speed that lets her finish? Nothing in the input is sorted. But you can ask a yes/no question about each speed: is it fast enough?

Pause and predict Piles [5, 9, 4, 11] and 8 hours. A pile of p takes ceil(p / k) hours. Is speed 5 fast enough?

This is called binary search on the answer. You need two things: a range of values that is sure to contain the answer, and a check for a single guess whose result is monotone. The check can cost O(n), because you run it only about log₂(size of the range) times.

When the array is rotated

A rotated sorted array, such as [12, 15, 18, 3, 5, 8, 10], is made of two sorted runs: a run of high values, then a run of low values that starts at the minimum. Compare each value with the last value of the array. "Is nums[i] at most 10?" is false on the high run and true on the low run, so the first true is the minimum.

Why compare with the last value? The last index always passes its own test, so a first true always exists, even when the array was not rotated at all. If you compared with nums[0] instead, an array that was not rotated, such as [4, 6, 9, 11], has no value below 4, so the question is never true and the same loop ends on 11 instead of 4.

The same search runs inside distributed stores: the server that owns a key on a consistent-hashing ring is the first server position at or after the key's hash. System design: partitioning

How to recognise it

The question to ask yourself: can you state a yes/no question whose answer flips exactly once as you move along the input, or along the range of possible answers?

Pause and predict In the sorted array [1, 3, 3, 5, 8, 8, 9, 12], the question is 'is nums[i] equal to 8?'. Can binary search find the 8s using that question?

Three that only look like it

• If you want a pair in a sorted array, such as two values with a given sum, each step can rule out one value, and one pass is O(n). That is two pointers, and it is simpler than running n binary searches.
• If the problem is a sequence of choices that you make once and never undo, that is greedy. The two techniques meet in Split Array Largest Sum, where a greedy check runs inside the binary search.
• If you need the k best items or a running median, the order keeps changing as items arrive. That is heaps.

Where it bites

Pause and predict In Java, lo = 1_500_000_000 and hi = 2_000_000_000, both ints. What is (lo + hi) / 2?

• Writing lo = mid. When two indices are left, mid rounds down to lo, so a false mid leaves the range unchanged. A mid known to be false must leave the range: lo = mid + 1.
• Mixing two templates. while (lo <= hi) belongs with hi = mid - 1 and a return inside the loop. Paired with hi = mid, it never stops. Learn one loop, and turn every question into a search for the first true.
• Starting hi at n - 1 when "none" is a possible answer. Search Insert Position must return n for a target larger than every value.
• A question that is not monotone. "Equal to the target" flips twice. Ask "at least the target" instead, then check the one index the search returns.
• The wrong range of answers. In Split Array Largest Sum, lo starts at the largest value in the array, because no limit below it can hold that value in any part.