Halving a list sounds almost too simple to get wrong, and yet you probably met an off-by-one bug or a loop that refused to stop somewhere in this section. That’s part of the deal with binary search!
The whole technique rests on one question you can answer at the midpoint, and that answer tells you which half can still hold what you’re looking for. Keep an invariant about the remaining interval, shrink it every round, and you reach the answer in O(log n) steps. Most bugs come from an interval that doesn’t shrink or an answer that slips outside it.
Here’s what each search was really looking for:
- Locate Ordered Value: Any match could end the search. Empty lists and endpoints tested your interval bounds.
- First Insertion Position: You searched for a boundary instead of a value, and the answer could be the length of the list.
- First Match: Finding the target didn’t end the search, because an earlier copy might still be hiding to the left.
- Last Match: The mirror image, with extra care to keep the interval shrinking when you moved right.
- Count Ordered Matches: Two boundary searches and a subtraction saved you from walking the run of matches.
- Minimum Processing Rate: You searched rates instead of indices. If a rate finishes in time, every faster rate does too, and that monotonic condition is what makes halving safe.
Keep in mind that sorted input is one way to get a monotonic condition, but it isn’t the definition. The last exercise didn’t have a sorted list to search at all.
