Searching
Linear Search Visualiser
Check every cell from the left until the value turns up.
Look for 18 by checking every cell from the left, stopping at the first match.
- Comparisons
- 0
- for scale
- n = 20
A value that is there sits about halfway along on average, so the count lands near half of n. The counter is an exact count for this run; the curve beside it is the shape that count follows as n grows, not a limit on it.
- Being compared
- Being written
- Pivot or smallest so far
- In its final place
- Ruled out
function linearSearch(a, target) { for (let i = 0; i < a.length; i++) { if (a[i] === target) return i; } return -1; // not here}The highlighted line is the one that produced the picture on the left.
What Linear Search does
Linear search is the search you would do by hand: start at the left, look at each value in turn, stop when you find the one you want. It asks nothing of the data — no order, no index, no preparation — and that is both its weakness and the reason it is sometimes the right answer.
How it works, step by step
- Start at index 0.
- Compare the value there with the target. If they match, return the index.
- Otherwise move one place right and compare again.
- If the end is reached with no match, the value is not in the array.
What to watch for
- The comparison count is the position of the value, so a target near the end costs nearly n comparisons and a missing value costs exactly n.
- Run the same search with binary search and compare the counters: around 20 comparisons against around 5 on a 20-cell array, and the gap widens fast as the array grows.
- Nothing is ever ruled out in advance. Every cell that has been passed was actually looked at.
Cost
| Best case | O(1) — the first cell |
|---|---|
| Average | O(n) |
| Worst case | O(n) — last cell, or missing |
| Extra space | O(1) |
| Needs sorting | No |
When to reach for it
On small arrays, on data that changes constantly, and whenever you would only search once — sorting an array to search it a single time costs more than just scanning it. It is also the only option when the data has no order to exploit.