Algorithms · Searching

Linear Search

The idea

Imagine looking for your friend in a cinema row, in the dark. You cannot see the whole row at once, so you walk along it, checking every single seat, until you find them. If they sit at the far end, you check the entire row.

The problem

You have a row of numbers and you want to find one particular value. Linear search is the most obvious idea there is: start at the left and check every item, one by one, until you hit the one you want.

Why it's slow

Linear search checked all 5 positions to find our target — it was hiding at the very end. With 100 items, a bad day costs 100 comparisons; with a million, a million. The work grows exactly as fast as the list does: that is O(n). It never needs the list to be sorted, though — that is its one superpower.

Pseudocode

  1. we are hunting one chosen value (the target)
    Explain this line

    The little "target" marker shows the value we are looking for.

  2. look at each position, one by one, from the left
    Explain this line

    No shortcuts: the pointer i visits positions strictly left to right.

  3. compare that item with the target
    Explain this line

    One comparison per visited position — count them!

  4. if they match — found it, stop
    Explain this line

    The search stops the moment the target is found.

Complexity

Best Average Worst Space
O(1) O(n) O(n) O(1)

Slow but humble: it needs no sorted list and no extra memory. Best case the target is the very first item you check.

Code

python 
def linear_search(a, target):
    for i, value in enumerate(a):
        if value == target:
            return i
    return -1
java 
int linearSearch(int[] a, int target) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == target) return i;
    }
    return -1;
}
cpp 
int linearSearch(const std::vector<int>& a, int target) {
    for (size_t i = 0; i < a.size(); ++i) {
        if (a[i] == target) return static_cast<int>(i);
    }
    return -1;
}
javascript 
function linearSearch(a, target) {
  for (let i = 0; i < a.length; i++) {
    if (a[i] === target) return i;
  }
  return -1;
}
dart 
int linearSearch(List<int> a, int target) {
  for (var i = 0; i < a.length; i++) {
    if (a[i] == target) return i;
  }
  return -1;
}

Quick check