Linear search (also called sequential search) is the algorithm that finds a target value by examining each element of a collection one after another, from the first position onward, until it finds a match or reaches the end. It needs no ordering and no auxiliary data structure, runs in O(n) time and O(1) extra space, and is the baseline against which all other search algorithms are measured.
In programming practice, linear search is far more common than its textbook reputation suggests. Methods such as indexOf, contains, find and the in operator on lists perform linear search, and for small or unsorted data it is often the fastest option in real hardware, not merely the simplest.
How linear search works step by step
The algorithm keeps a single index and compares the element at that index with the target. If they are equal, it returns the index; otherwise it advances. If the index passes the last element, it returns a not-found signal, typically -1, null or an empty optional.
- Set the index to the first position of the collection.
- Compare the current element with the target using the equality test of the data type.
- If the comparison succeeds, return the current position.
- Otherwise move to the next position and repeat.
- When no positions remain, report that the target is absent.
The method works on any structure that can be traversed in order, including arrays, linked lists, streams and files. That generality is its main strength: binary search requires sorted, randomly accessible data, while linear search only requires a way to visit each element once.
Time and space complexity
The cost of linear search is counted in comparisons. In terms of Big O notation, its time complexity grows linearly with the number of elements n, while its space complexity stays constant because only an index and the target are stored.
| Case | Comparisons | When it happens |
|---|---|---|
| Best case | 1 | Target is the first element |
| Average case (present) | About (n + 1) / 2 | Target equally likely at any position |
| Worst case (present) | n | Target is the last element |
| Target absent | n | Every element must be checked |
The unsuccessful search is always the expensive case, because absence can only be proven by checking everything. This matters for workloads such as duplicate checks or permission lookups, where most queries end without a match.
Linear search compared with other search methods
Linear search is the right choice when preparation costs more than it saves. Faster methods require sorting or building an index first, which only pays off when many searches run on the same data.
| Method | Lookup time | Requirement |
|---|---|---|
| Linear search | O(n) | None, any traversable collection |
| Binary search | O(log n) | Sorted data with random access |
| Hash table lookup | O(1) on average | Hash function and extra memory |
| Balanced search tree | O(log n) | Tree maintained on every insert |
| Interpolation search | About O(log log n) on uniform data | Sorted, evenly distributed numeric keys |
A useful rule of thumb follows from these costs. Sorting costs O(n log n), so for k searches on the same data, sorting plus binary search wins only when k is large enough to amortize the sort. For a single search on unsorted data, linear search is optimal in the comparison model, because any correct algorithm must potentially examine every element.
Variants and optimizations
Several variants reduce the constant factor without changing the linear growth. They are worthwhile in hot code paths and in embedded systems where every comparison counts.
| Variant | Idea | Benefit |
|---|---|---|
| Sentinel search | Place the target after the last element | Removes the bounds check from the loop |
| Early exit on sorted data | Stop when elements exceed the target | Faster unsuccessful searches |
| Move-to-front | Move found items to the start | Frequent targets found sooner |
| Transposition | Swap found item with its predecessor | Gradual adaptation to access patterns |
| Vectorized search | Compare several elements per SIMD instruction | Large constant-factor speedup |
Self-organizing lists using move-to-front or transposition exploit skewed access frequencies: when a few items account for most lookups, the average search becomes much shorter than n / 2. Parallel linear search splits the collection among threads, which helps on very large arrays but adds coordination overhead.
When linear search is the better choice
On modern processors, linear search over a contiguous array benefits from cache locality and hardware prefetching, while binary search jumps across memory and suffers from branch mispredictions. For arrays of roughly a few dozen to a few hundred small elements, a tight linear scan frequently matches or beats binary search; the exact crossover depends on element size and hardware and should be measured.
- Small collections, such as configuration options or short lookup tables.
- Unsorted or frequently changing data where maintaining order would cost more than scanning.
- One-off searches in logs, files or streams processed once.
- Searching by a complex condition rather than a key, such as the first order above a given amount.
Pitfalls in real code
The most frequent problem is accidental quadratic time: calling a linear search inside a loop over another collection turns an O(n) operation into O(n × m). Checking whether each of 100,000 incoming identifiers appears in a list of 100,000 known identifiers means up to ten billion comparisons, while a hash set reduces the job to about 100,000 lookups.
Other errors include off-by-one bounds that skip the last element, using reference equality instead of value equality, and confusing a returned index of 0 with failure in languages where 0 is falsy. Clear return conventions and tests for empty collections, first and last positions and absent targets prevent most of them.
A non-technical view
Linear search is the way people look for something when nothing is organized: check the first item, then the next, and keep going until you find it or run out of items. Looking for a particular receipt in an unsorted shoebox works exactly like this.
It always works, and for a small box it is quick. The problem appears when the box is huge or you need to search it again and again. Then it pays to sort or label things first, so you can jump straight to the right place instead of going through everything each time.
A concrete example
A developer maintains a nightly import job that checks whether each of 200,000 product codes from a supplier already exists in the shop catalog. The original code stores existing codes in a list and calls contains for every incoming code, which performs a linear search each time. The job takes more than an hour.
The developer keeps linear search where it fits, for scanning the 12 entries of a currency table, but replaces the catalog list with a hash set built once at the start. The number of comparisons falls from billions to a few hundred thousand, and the job finishes in under a minute. The fix illustrates the core lesson: linear search is excellent for one pass, and costly when repeated inside another loop.