Linear Search

Introduction

Linear Search is the simplest searching algorithm — it checks every element in a collection one by one until it finds the target or reaches the end. It’s like looking for a specific book on an unsorted shelf by scanning from left to right.

It’s not the fastest search, but it works on any collection — sorted or unsorted, arrays or linked lists. Understanding Linear Search also helps you appreciate why Binary Search is so much faster on sorted data. You should be comfortable with Arrays and Big-O Notation before reading this.

How it works

Find 7 in [3, 8, 1, 7, 2, 9]

[3, 8, 1, 7, 2, 9]
 ^                    3 ≠ 7
    ^                 8 ≠ 7
       ^              1 ≠ 7
          ^           7 = 7 ✓ → found at index 3

Implementation

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

console.log(linearSearch([3, 8, 1, 7, 2, 9], 7));   // 3
console.log(linearSearch([3, 8, 1, 7, 2, 9], 5));   // -1

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

print(linear_search([3, 8, 1, 7, 2, 9], 7))   # 3
print(linear_search([3, 8, 1, 7, 2, 9], 5))   # -1

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

System.out.println(linearSearch(new int[]{3, 8, 1, 7, 2, 9}, 7));  // 3
System.out.println(linearSearch(new int[]{3, 8, 1, 7, 2, 9}, 5));  // -1

Variations

Find all occurrences

function findAll(arr, target) {
  const indices = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) indices.push(i);
  }
  return indices;
}

console.log(findAll([1, 3, 5, 3, 7, 3], 3));  // [1, 3, 5]

Search in objects

function findByProperty(arr, key, value) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i][key] === value) return arr[i];
  }
  return null;
}

const users = [
  { id: 1, name: 'Alice' },
  { id: 2, name: 'Bob' },
  { id: 3, name: 'Charlie' },
];
console.log(findByProperty(users, 'name', 'Bob'));  // { id: 2, name: 'Bob' }

Sentinel Linear Search

An optimization that eliminates the bounds check on every iteration by placing the target at the end:

function sentinelSearch(arr, target) {
  const n = arr.length;
  const last = arr[n - 1];

  arr[n - 1] = target; // place sentinel

  let i = 0;
  while (arr[i] !== target) i++;

  arr[n - 1] = last; // restore

  if (i < n - 1 || last === target) return i;
  return -1;
}

This removes one comparison per iteration (no i < arr.length check). The improvement is marginal in practice but shows up in interview discussions about micro-optimizations.

Complexity analysis

Space: O(1) — no extra memory needed.

Linear Search vs Binary Search

If your data is sorted, always prefer Binary Search. If it’s unsorted and you’re searching once, Linear Search is your only option. If you’re searching many times, consider sorting first and then using Binary Search.

Practice problems

1. Find the index of the first occurrence of a value
2. Count occurrences of a value in an array
3. Find the minimum/maximum in an unsorted array
4. Search in a 2D matrix (unsorted)
5. Two Sum (brute force approach uses nested linear search)