Binary Search: Halving the Search Space

Searching a sorted list, you don't need to check every item one by one. Look at the middle item instead. If it matches, you're done. If the target is smaller, everything to the right of the middle is too big to matter, so throw it all away in one move. If the target is bigger, throw away everything to the left. Either way, one comparison eliminates half the remaining list. That's the whole trick: sorted order lets you make a decision about an entire half without checking each item in it.

This is why binary search beats checking items from one end: a linear search might need to look at every single item, but binary search needs only about log base 2 of n comparisons. A list of a million sorted items takes at most about 20 comparisons, not a million. Each round the problem size shrinks by half, so the work shrinks fast even as the list grows huge.

Binary search sits next to linear search as the course's go-to contrast for runtime: linear search works on any list but scales poorly, binary search scales beautifully but demands sorted data first. That tradeoff connects forward to the idea of algorithmic efficiency and why some problems need preprocessing, like sorting, before a faster algorithm becomes possible at all.