Linear Search: The Simplest Search Algorithm

Linear search (also called sequential search) finds a target by checking each element one at a time, from the start until it finds a match or runs out of elements. It’s the simplest possible search and the only option when your data is unsorted — because the target could be anywhere, you have no choice but to look everywhere.

How it works

Walk the collection from index 0 upward. Compare each element to the target. Return its index the moment you find a match; if the loop finishes with no match, return -1 (a sentinel meaning “not found”).

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

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

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

def linear_search(a, target):
    for i, v in enumerate(a):
        if v == target:
            return i      # found
    return -1             # not found

Complexity

Space is O(1) — it scans in place with a single index. There’s no preprocessing, so it works on any data, in any order, immediately.

For beginners: “Sentinel” just means a special return value that can’t be a real index. We use -1 because valid indices start at 0.

When linear search is the right call

Linear search loses to binary search on large sorted data, but it wins in several real situations:

• Unsorted data searched only once or twice — sorting first (O(n log n)) wouldn’t pay off.
• Small inputs (a few dozen elements) — the simplicity beats the overhead and bug-risk of anything fancier.
• Linked structures with no random access, like a singly linked list, where you can only step forward one node at a time.
• Finding all matches, or matching on a complex condition, not just one sorted key.

Beyond “find the index”

The same single-pass shape powers many one-liners: count occurrences, find the min/max, or locate the first element satisfying a predicate. Most languages ship built-ins for these — std::find (C++), indexOf (JS), list.index (Python) — but they’re all linear search under the hood.

Going deeper: If you find yourself running linear search over the same collection again and again, that’s a signal to change the data structure: sort it once and use binary search, or load it into a hash set for average O(1) membership.

Next: unlock O(log n) lookups with binary search, or jump to the searching exercises.