Linear Search

The problem

Your phone shows an unsorted list of 300 contacts and you need to find "Priya". There's no alphabetical order to lean on — names arrived in whatever order you saved them. So what do you actually do? You start at the top and read down: Aman, no. Zoya, no. Ben, no… until Priya's name appears or the list runs out.

That's not a clever trick. It's the most honest thing you can do when the data has no structure. And it's worth understanding precisely, because it's the yardstick every faster search — binary search, hashing, trees — is measured against.

A first attempt

Maybe you think: sort the contacts first, then I can jump around cleverly. Sorting 300 names costs O(n log n), and then you still have to search. For a single lookup that's pure waste — you paid to reorganize the whole list to find one name once.

If you're only searching once, and the data isn't already sorted, there's nothing to exploit. You have to look. The only question is how to look cleanly.

The insight

When data is unordered, any element could be the target, so you cannot safely skip a single one. Checking every element until you hit the target (or the end) is not just a solution — it's provably the best you can do on unsorted data. That's O(n).

The one improvement worth making: stop the moment you find it. On average you'll examine half the list, and if the item is missing you'll examine all of it. Name it now — this is linear search.

How it works

Searching for target = 9:

index:   0   1   2   3   4
value:   4   9   2   7   1
         ^  4 ≠ 9, step right
             ^  9 = 9  ✓ found at index 1

The code

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

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

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

int linear_search(const int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

int linearSearch(const std::vector<int>& arr, int target) {
    for (int i = 0; i < (int)arr.size(); i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

Complexity

Best case is O(1) (the target is first); average is O(n/2), which is still O(n).

When to use it

Practice

Recap

• Linear search checks each element in turn and stops at the first match — O(n) time, O(1) space, no preconditions.
• It's optimal on unsorted data: with no structure to exploit, you can't skip elements.
• It's the baseline every faster search must beat — the moment data is sorted or indexed, switch to something smarter.