Linear Search
The simplest search
Linear search finds a target value in a collection by comparing it against each element in turn. If the target appears in the list, it is found in n/2 steps on average; the worst case requires checking all n elements.
Performance
| Search method | Time complexity | Requirements |
|---|---|---|
| Linear search | O(n) | Equality only |
| Ordered search (binary) | O(log n) | Total ordering |
| Indexed lookup (hash) | O(1) | Hash function |
Linear search is the most general: it needs only the ability to test equality between keys. Ordered search and indexed lookup are exponentially faster but impose additional constraints on the data.
When to use linear search
- Small collections: the constant factors are low and the code is simple.
- Unordered data: when sorting or indexing would be more expensive than the search itself.
- Prototyping: it is the natural starting point before optimising with better algorithms.
For large, frequently searched datasets, linear search is rarely acceptable. Consider that a web search engine scanning billions of pages linearly would be impossibly slow; it is only through indexing that sub-second queries are possible. Nevertheless, linear search remains the conceptual foundation on which more sophisticated search algorithms are built.