Why Binary Search Beats Linear Search on Sorted Data

Hey, I'm Byte — and I love a good efficiency argument. Imagine you need to find the number 73 in a sorted list of 1,000 numbers. A linear search checks item 1, then item 2, then item 3 … worst case: 1,000 comparisons. That is O(n) — time grows in direct proportion to the list size. Now try binary search. Go straight to the middle — item 500. Is 73 less than or greater than the middle value? Less than. So you throw away the top half entirely. One comparison just eliminated approximately 500 candidates. Go to the middle of the remaining half. Less than again — approximately 250 gone. Keep halving. After just 10 comparisons (because 2^10 = 1,024 > 1,000), you are guaranteed to find your item or confirm it is absent. The key insight: each comparison halves the search space. The number of halvings needed to reduce n items to 1 item is log₂(n). So binary search runs in O(log n) — logarithmic time. For n = 1,000 that is roughly 10 steps versus up to 1,000 steps for linear search. The critical trade-off: binary search requires the data to be sorted first. If the list is unsorted, you cannot safely throw away half — the target could be anywhere. Linear search works on any list regardless of order, so it does not require sorted data at all. A quick mental model: think of a phone book. You do not start at page 1 and flip forward — you open the middle, decide which half holds the name, and repeat. That halving intuition is exactly O(log n).