Linear Search
Linear search is the algorithm you already use without thinking: look at each item, one by one, until you find what you want or run out of items. It needs nothing - no sorted data, no extra structures - and it is the honest baseline every other search is measured against. On unsorted data, it is also the best you can possibly do.
Watch it search
Press play - or drag the timeline and step through it yourself.Find 47 among 18 values. No shortcuts possible - the array is not sorted, so check one by one.
Complexity
Finding your keys
You lost your keys somewhere in the house. There is no clever trick: you check the kitchen, then the sofa, then the coat pocket - one place at a time, until they turn up. If the house had an index ("keys are always on the hook"), you would use it. But without order, checking everywhere is not dumb - it is the only correct plan. That is linear search.
How it works, step by step
Start at the first item.
Is it the one you want? If yes - done, return its position.
If not, move one step right and check again.
If you reach the end without a match, the item is not there - report that honestly (in JavaScript: −1).
Best case: the first item matches (1 check). Worst case: it is last, or missing (n checks).
On average, a present item is found after about n/2 checks.
The code, in JavaScript
The whole algorithm in five lines. Returns the index, or -1 - the same contract as JavaScript's built-in indexOf.
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i; // found - report where
}
return -1; // not found
}
linearSearch([7, 3, 9, 4], 9); // → 2
linearSearch([7, 3, 9, 4], 5); // → -1Dry run: searching in [7, 3, 9, 4, 9]
The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.
| Step | Check | Array | What happened |
|---|---|---|---|
| 1 | 1 | [7, 3, 9, 4, 9] | Position 1: 7 - not 4, keep going. |
| 2 | 2 | [7, 3, 9, 4, 9] | Position 2: 3 - not 4, keep going. |
| 3 | 3 | [7, 3, 9, 4, 9] | Position 3: 9 - not 4, keep going. |
| 4 | 4 | [7, 3, 9, 4, 9] | Position 4: 4 - that is the target! Found after 4 check(s). |
Good choice when…
- The data is unsorted and searched rarely - scanning once is cheaper than sorting first (O(n) beats O(n log n) + O(log n)).
- The list is small - under ~100 items, nothing beats a simple scan in practice.
- You search by an arbitrary condition (`find(u => u.age > 30)`) - order cannot help with a rule like that.
- Data arrives as a stream you see once - linear scanning is the only option anyway.
Bad choice when…
- The data is sorted and you search often - binary search does it in O(log n): 20 checks instead of a million.
- You do many lookups by the same key - build a Map/Set once (O(n)) and every lookup after that is O(1).
- It sits inside another loop over the same data - `for x of xs: ys.includes(x)` is the classic hidden O(n²).
Common mistakes
- The #1 real-world bug is not in the search - it is calling it in a loop. `array.includes()` inside `for` = O(n²); at 10,000 items that is 100 million checks. Swap in a Set and it collapses to O(n).
- `indexOf` uses strict equality - it cannot find objects by content (`[{a:1}].indexOf({a:1})` is −1). Use `findIndex` with a test function for objects.
- `indexOf` returns −1, not undefined or null. Forgetting the `!== -1` check and treating −1 as truthy (`if (idx)`) also misfires when the item is at position 0.
- `find` returns `undefined` both when nothing matched and when the stored value itself was `undefined` - if that difference matters, use `findIndex`.
Linear Search vs. its closest relatives
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Linear Searchthis page | O(1) | O(n) | O(n) | O(1) | - |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) | - |
| Two Pointers | O(n) | O(n) | O(n) | O(1) | - |
| Sliding Window | O(n) | O(n) | O(n) | O(k) | - |