Linear Search

Scan an array from the first element to the last until the target turns up — works on any list, sorted or not.

Linear search is the most basic way to find something: start at the first element and check each one in turn until you hit the target or run off the end. It needs *no setup* and makes *no assumptions* — the list can be sorted, shuffled, or full of duplicates and it still works. That generality is its whole appeal, and the price you pay is speed.

The scan, step by step

1Start at index 0 — the first element.
2Compare the current element with the target.
3If they match → return the index. Done.
4If not, step one position right and compare again.
5If you walk off the end without a match → the target isn't there; return -1.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i; // found
  }
  return -1; // ran off the end
}

Why 'on average, half the list'

If the target is equally likely to sit anywhere, you find it after scanning about n/2 elements on average — and all n in the worst case (target last, or absent). Both are O(n): the work grows in lockstep with the list's size.

When linear search is the right call

It sounds primitive, but linear search wins in several real cases. On an unsorted list it's the *only* option without sorting first. On a tiny list the simplicity beats the overhead of anything cleverer. And it accesses memory sequentially, front to back, which is exactly the pattern CPU caches are built for — so a linear scan over a small array can outrun a binary search's jumping around.

Don't sort just to search once

Sorting costs O(n log n). If you only need to find one element one time, a single O(n) linear scan is cheaper than sorting first and then binary-searching. Sort only when you'll search the same data many times.

OperationTimeSpace

Best case · target is the first elementO(1)O(1)

Average / worst · ~n/2 on average, all n if absentO(n)O(1)

Check yourself

What is the key advantage linear search has over binary search?