Searching Algorithms
An overview of searching — what it means to search, the two fundamental strategies, and how to choose between them.
Searching is the act of locating a specific element within a collection. It is one of the most common operations in computing — looking up a user record, checking if a key exists in a cache, finding a value in a sorted index.
Every search algorithm makes a tradeoff between preconditions (does the data need to be sorted?), time per search, and cost of preparation. The two fundamental strategies are: scan everything in sequence (linear search), or exploit sorted order to eliminate half the remaining candidates with each step (binary search). This article covers both in full detail.
Comparison: Linear Search vs Binary Search
| Property | Linear Search | Binary Search |
|---|---|---|
| Precondition | None — works on any data | Array must be sorted |
| Best case | O(1) — target at index 0 | O(1) — target at initial midpoint |
| Average case | O(n) | O(log n) |
| Worst case | O(n) | O(log n) |
| Space (iterative) | O(1) | O(1) |
| Space (recursive) | O(n) | O(log n) |
| Preparation cost | O(0) | O(n log n) to sort |
| Handles duplicates | Yes, finds first occurrence naturally | Requires variants (first/last occurrence) |
| Works on linked lists | Yes | No — requires random access |
| Predictability | Variable (depends on target position) | Highly predictable (always ≤ log₂(n) steps) |
| Suitable for tiny arrays | Yes — cache-friendly | Linear search often faster for n < ~16 |
| Suitable for large static datasets | No | Yes |
When to sort and use binary search: if you run k searches on a dataset of size n, binary search becomes worthwhile when the sort cost amortizes across queries. Sorting costs O(n log n); each binary search costs O(log n); each linear search costs O(n). The crossover: k × O(n) > O(n log n) + k × O(log n), which simplifies to k >> log n. For most real workloads where searches vastly outnumber insertions, binary search wins decisively.