The test that switches once

Lesson · 9 min read · Binary search · Introduction to binary search

Every binary search is the same search: candidates in a line and a yes/no test that is false up to a point and true after it. Learn to see the test.

Candidates in a line, one question

Strip any binary search down and two things are left. There is a line of candidates: indices of an array, capacities from 1 to a million, days, distances. And there is a yes/no test on a candidate that reads false, false, …, false, true, true, …, true along the line. The search finds where the answers switch.

The test "a[i] ≥ 23" along a sorted array: false for the first four indices, true for the rest. The switch is at index 4.

Each test at the middle of the range tells you which side of the middle the switch is on. That is the only reason the method works, and it is why the condition to look for is not "sorted" but a test that switches exactly once. Sortedness is one way to get such a test. There are others.

Three places the switch hides

Step 1 / 3

In the data. A sorted array and a threshold: "is a[i] at least the target?" The first true is where the target is, or where it would go.
Step 2 / 3

In the answer. Ship capacities 1 to 30 and the test "can this capacity clear the backlog in 5 days?" Too small fails, large enough passes, and every larger one passes too. The first pass, 15 here, is the answer. No array is searched at all.
Step 3 / 3

In the structure. A mountain array is not sorted, but "is the next element smaller?" is false all the way up and true all the way down. The first true is the peak.

Interview problems are mostly the second and third kind dressed up as something else. The array problems are the warm-up.

When there is no switch

Run the same search on a test that switches more than once and it still returns an index, which is what makes the bug dangerous: nothing crashes.

An unsorted array and the test "a[i] ≥ 7": F T F T F T F F. There is no single boundary.

So before writing a search, say the test out loud and say why it cannot switch back. "If capacity c works, c + 1 works too, because a bigger ship can carry every load the smaller one did." That sentence is the proof the interviewer is listening for.

The first-true search from the previous lesson, run on that test.

Step 1 / 5

lo0hi8
Find the first index with a[i] ≥ 7. The answer, by eye, is 1.
Step 2 / 5

lo0mid4hi8
a[4] = 1: fails, so the search concludes everything up to 4 fails: lo = 5.
Step 3 / 5

lo5mid6hi8
a[6] = 3: fails, so the search concludes everything up to 6 fails: lo = 7.
Step 4 / 5

lo7mid7hi8
a[7] = 6: fails, so the search concludes everything up to 7 fails: lo = 8.
Step 5 / 5

returned8
It returns 8, meaning "nothing passes", although indices 1, 3 and 5 pass. Each step assumed the test could not switch back, and here it can.

test falsetest truebeing tested

The questions to ask

When a problem looks like a search, these four questions settle it.

Question	What it gives you
What are the candidates, in order?	The range: indices, values, capacities, times, distances.
What is the yes/no test on one candidate?	The check you will call log n times. Its cost sets the total.
Why can it not switch back?	The monotonicity argument. Without it the search is not valid.
First true or last true?	Minimising wants the first true; maximising wants the last. This decides the template.

If you cannot answer the third question, binary search is the wrong tool. The usual alternatives are a hash map, two pointers, or a scan.