Linear Search is the most fundamental search algorithm. It scans every element of a list one by one from left to right until it finds the target or runs out of list.

There are no preconditions and no sorting step. You just iterate and compare.

text

Why Use It?#

Linear search shines in situations where:

  • The array is unsorted (binary search can't help you)
  • The array is very small (overhead of sorting isn't worth it)
  • You need to find the first element matching a condition, not just an exact value

The Algorithm#

  1. Start at index 0
  2. Compare nums[i] with target
  3. If they match, return i
  4. Otherwise increment i and repeat
  5. If the end is reached, return -1
  • Time Complexity: O(N), since in the worst case we check every element
  • Space Complexity: O(1), with no extra memory needed

Interactive Lab#

Let's take the example in the visualization below: the array [2, 5, 8, 13, 21, 34, 55, 89, 144] with target = 21. Press play and follow the single moving pointer.

It compares 2, then 5, then 8, then 13 (four misses, each one dimming out behind the pointer) and lands on 21 at index 4 on the fifth comparison. Four of the nine elements are never even looked at, because linear search stops the instant it matches.

Notice what the algorithm doesn't do: this particular array happens to be in ascending order, but the pointer still walks it one slot at a time. Linear search neither knows nor cares whether the input is sorted. That indifference is exactly why it works everywhere, and exactly why it can't do better than O(N).

ScenarioBest Choice
Unsorted arrayLinear Search
Sorted array, large NBinary Search
Tiny array (< 10 elements)Linear Search (simpler)
Searching by a condition (not exact match)Linear Search

What to Remember#

Linear search is the algorithm you instinctively perform when scanning a list by eye. It's O(N), meaning doubling the input doubles the work. For large sorted datasets, use Binary Search instead. But for small or unsorted data, linear search is perfectly fine.