P-5.4 Searching and Binary Search

What this is and why it exists

Binary search is the shortest famous algorithm that almost nobody writes correctly on the first attempt. That makes it an excellent lesson in boundary conditions.

But the more valuable idea sits behind it. Any question whose answer is *no* up to some point and *yes* after it can be searched the same way. Even when there is no array anywhere in sight.

That reframing turns a surprising number of hard-looking problems into about ten lines.

The vocabulary

• Linear search — scanning from one end.
• Binary search — halving the remaining range at each step.
• Invariant — something true before and after every step of the loop.
• Half-open range — a convention where one end is included and the other is not.
• Monotone property — one that is false up to a point and true thereafter.
• Predicate — the yes-or-no test being searched against.

The mental model

First, know when not to bother. For small collections, unsorted data, or a single lookup, scanning is faster than any preparation you could do first. Sorting in order to search once is a loss, and it is a common one.

Binary search halves the remaining range each step, and it needs sorted input. The famous difficulty is entirely about boundaries: whether each end of your range is included, and how the midpoint moves. Decide your convention before writing the loop. Pick half-open or fully closed, write it down, and be consistent. Almost every classic mistake with this algorithm comes from changing convention halfway through the function without noticing.

The more useful form is not exact-match at all. It looks for the boundary — the first item that satisfies a condition. That variant answers far more real questions than exact match ever does. The first log entry after a timestamp, the first version that fails, the insertion point for a new item.

And then the generalisation. Suppose a candidate answer can be tested as "too small" or "large enough". Then the range of possible *answers* can be halved, even though no array exists at all. This is where the technique earns its reputation. Problems asking for the smallest capacity that works, or the least time needed, become searches over the answer. The test does the real work.

Write it once with no off-by-one errors, and test five cases. An empty input, one element, the first position, the last position, and a value that is absent. Those five catch nearly every mistake this algorithm invites.

What you should now be able to explain or do

Say when scanning beats searching, and why sorting to search once is a loss. Write a binary search with a convention decided in advance and held to. Write the boundary-finding form and say why it answers more real questions. Recognise a problem that can be searched over its answer rather than over an array. Test the five edge cases.

Check yourself