Binary Search: Halving the Range

Binary search works because sorted order lets one comparison do the work of many. Check the middle element: if it's the target, you're done. If the target is smaller, every element to the right of the middle is also too big, so the entire right half disappears in one move. If the target is larger, the entire left half disappears. Either way, one comparison kills half the remaining candidates, not just one candidate.

That halving is why binary search scales so well. A million names takes at most about twenty comparisons, because a million halved twenty times shrinks to roughly one. Each comparison multiplies your progress instead of adding to it: going from n items to n/2, then n/4, then n/8 reaches 1 after about log2(n) steps. Linear search, by contrast, checks elements one at a time and in the worst case looks at every single one, so it needs up to n comparisons. For ten items that difference barely matters; for a million items it's the difference between about twenty looks and a million.

The method depends completely on order. The decision to discard a half rests on assuming everything on one side of the middle is smaller and everything on the other side is larger. On unsorted data that assumption can be false, so the discarded half might actually hold the target. This is also why binary search sits next to sorting in this unit: the sort does the expensive work once, and binary search cashes in on it over and over with cheap, fast lookups.