Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Searching

Linear Search Visualiser

Check every cell from the left until the value turns up.

Search forTarget: 18

Look for 18 by checking every cell from the left, stopping at the first match.

Comparisons
0
for scale
n = 20
AverageO(n)extra space O(1)

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

  1. Start at index 0.
  2. Compare the value there with the target. If they match, return the index.
  3. Otherwise move one place right and compare again.
  4. 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 caseO(1) — the first cell
AverageO(n)
Worst caseO(n) — last cell, or missing
Extra spaceO(1)
Needs sortingNo

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.

Read more