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
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
More options
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 |
Scroll the table sideways for the rest of the columns.
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) |
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, so a linked list or a stream works the same way. You pay for that generality by having no way to skip anything.
Implementation
function linearSearch(values, target) {
for (let i = 0; i < values.length; i += 1) {
if (values[i] === target) return i;
}
return -1;
}When 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 what binary search is for.