Searching Strategies

Finding a Needle

Searching asks: is a target present in a collection, and where? The strategy depends entirely on whether the data is sorted.

Linear search scans elements one by one from the start until it finds the target or reaches the end. It works on any collection, sorted or not, and is $O(n)$ in the worst case (the target is last or absent). It is the only option for unsorted data and is perfectly reasonable for small collections.

Binary search exploits sorted order to do far better. It compares the target to the middle element: if equal, done; if the target is smaller, discard the entire upper half and search the lower; if larger, discard the lower half. Each comparison halves the remaining range, so binary search is $O(\log n)$ — for a million elements, about 20 comparisons instead of a million. The catch is that it requires the data to be sorted, and only supports structures with fast random access (like arrays).

The deeper lesson is that structure enables efficiency: sorting the data first (an $O(n \log n)$ cost paid once) makes every subsequent search $O(\log n)$ instead of $O(n)$. If you search a fixed dataset many times, that one-time sort pays for itself many times over — a classic case of investing structure to buy speed.

Common pitfall: running binary search on unsorted data. Binary search's correctness depends on the sorted invariant — if the data is not sorted, discarding "the half that cannot contain the target" is invalid, and it will silently miss present elements. Verify the data is sorted (or sort it first) before using binary search.

A sorted array bar with binary search halving the highlighted range in accent at each step — full, then half, then quarter — converging on the target, while a side counter tallies log2(n) comparisons.

$$\text{binary search} = O(\log_2 n)$$