Home/Searching/Linear search
Search algorithmsCTRL K

Linear search

· sequential scan · no preconditions
/searching/linear-search
COMPARISONS
0
one per element checked
INDEX
—
position being checked
TARGET
33
value we look for
CHECKED
0/ 32
elements seen so far
RESULT
—
index once found
probetargetfound
n = 32 · target 33 · seed 7 · 12 steps
step 0 / 11
Size32
linear_search.ts
1
function linearSearch(array: number[], target: number) {
2
  for (let index = 0; index < array.length; index++) {
3
    if (array[index] === target) return index;
4
  }
5
  return -1;
6
}
CURRENT STEP
line 1

Look for 33 in 32 elements, from the first one on.

// how it works

Understanding Linear search

linear search · look at everything, one at a time
01

The idea

Linear search checks the elements one by one, from the first, until it finds the target or runs out. It asks nothing of the data: not sorted, not indexed, not even in memory, a stream works.

The cost is proportional to the position of the target: n/2 comparisons on average when it is present, n when it is not. That is fine for a few hundred elements or a single lookup, and hopeless for a million lookups in a million elements.

02

The four stages

1
probelook at array[index]
2
compareis it the target?
3
advancei ← i + 1
4
foundreturn i, or −1 at the end
03

Complexity

best
O(1)target is the first element
average
O(n)n/2 comparisons when present
worst
O(n)target last, or absent
space
O(1)one index
04

Versus its siblings

COMPARISONS AT N = 1 000 · TARGET PRESENT
linear
500
jump
63
binary
10
interpolation
4
hash table
1
average over random targets · sorted input for all but linear
05

Pseudocode

LINEARSEARCH(array, target)
  for index ← 0 to n − 1
    if array[index] = target: return index
  return −1
06

When to use

Unsorted or tiny collections, a single lookup, or data you can only read once from front to back.
As the inner loop of everything else: a block scan inside jump search, a bucket walk inside a hash table.
07

Pitfalls

Repeated lookups in the same array: sort it once and use binary search, or build a hash table.
Comparing objects field by field inside the loop hides an O(n · k) cost; compare a key.
A sentinel at the end removes the bounds check but is easy to forget to remove.
08

History

Linear search is as old as lists themselves; Knuth's 1973 volume on searching opens with it as the baseline every other method is measured against, and the sentinel trick that saves the bounds check is one of the first optimisations he presents.

Back to Searching