Linear search

O(n)

Linear search is the simplest search: walk the array element by element and compare each with the target. It works on any list (sorted or not) and runs in O(n). It is the right choice for small or unsorted data, where the overhead of sorting for a faster search isn't worth it.

Array
Edit the input and press Play

How it works

  1. Start at the first element.
  2. Compare it with the target; if equal, you're done.
  3. Otherwise move one step right and repeat.
  4. If you reach the end without a match, the value isn't present.

Pseudocode

1linearSearch(a, target):            # O(n)2  for i from 0 to n-1:3    if a[i] = target: return i4  return -1