Searching Strategies

Finding a Needle

Searching asks whether a target is present in a collection and where it lives. The right 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 hits the end. It works on any collection, has a worst-case time of $O(n)$, and is the only choice for unsorted data.

Linear search is fine for small collections, but large datasets demand a faster approach.

Binary Search

Binary search exploits sorted order by comparing the target to the middle element. If smaller, it discards the upper half; if larger, it discards the lower half. Each step halves the range, yielding $O(\log n)$ time.

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

Structure enables efficiency: sorting once makes future searches $O(\log n)$.

Common pitfall: Running binary search on unsorted data. Its correctness depends on the sorted invariant; without it, discarding halves will silently miss present elements. Always verify sorted status first.