How Linear Search Works
Linear search checks each element in turn. It is the only search that needs no order at all, and the baseline every other search has to beat.
- Ruled out
- Still possible
- Checked now
- Found
Step 1 of 15
Looking for 158 in 16 sorted values, from 4 to 196.
Counters
- Steps
- 0
- Result
- -
- Still possible
- 16
- of 16
- Worst case
- 16
- steps for this size
Settings
Two to 64 numbers. Sorted ascending before the search runs.
Linear search
- 1
for i in 0..n-1: - 2
if a[i] == target: - 3
return i - 4
if a[i] > target: - 5
return NOT_FOUND // sorted - 6
return NOT_FOUND
The same array, every algorithm
Probes on the values above, cheapest first. One probe is one value actually looked at.
- Interpolation1
- Ternary3
- Binary4
- Jump5
- Exponential8
- Linear13
How the six compare
| Algorithm | Best | Average | Worst | Needs a sorted array |
|---|---|---|---|---|
| Linear | O(1) | O(n) | O(n) | No |
| Binary | O(1) | O(log n) | O(log n) | Yes |
| Ternary | O(1) | O(log n) | O(log n) | Yes |
| Jump | O(1) | O(√n) | O(√n) | Yes |
| Exponential | O(1) | O(log n) | O(log n) | Yes |
| Interpolation | O(1) | O(log log n)* | O(n) | Yes |
Interpolation search only reaches that average when the gaps between the values are even.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(1) | O(n) | O(n) | O(1) |
On average it looks at half the list when the value is present, and all of it when it is not.
How linear search works
Linear search walks the list from one end, comparing each element with the target, and stops at the first match. It makes no assumptions: the data need not be sorted, indexed or even random-access — a linked list or a stream works the same way. That generality is the whole point, and the cost is that it has no way to skip anything.
- Start at the first element.
- Compare it with the target. If they match, return the index.
- Otherwise move to the next element.
- If the end is reached without a match, the value is not present.
Implementation
The same algorithm the visualiser is running, written to be read.
def linear_search(values, target):
for i, value in enumerate(values):
if value == target:
return i
return -1When to use it
- Use it on unsorted data, which is most data. Sorting a list to binary search it once costs more than scanning it.
- Use it on small collections, where the constant factors dominate and a scan of twenty elements beats any cleverness.
- Use it when the data arrives as a stream and you cannot jump around it at all.
- Avoid it on large sorted collections you search repeatedly — that is precisely what binary search is for.
Check yourself
If the animation made sense, these should too.
When does searching a sorted array with a linear scan beat binary search?
When the array is small enough that the constant factors dominate, when the data cannot be randomly accessed - a linked list or a stream - and when the collection would have to be sorted first: sorting is O(n log n), so a one-off search should just scan.
Why is the average cost n/2 for a hit but n for a miss?
A hit stops at the target, which is on average halfway along if every position is equally likely. A miss has no early exit - it has to look at every element to prove the value is absent.