Linear Search Explained: When O(n) Is the Right Call

Linear search is the algorithm everyone already knows: look at each item in turn until you find the one you want or run out. It is also the one most people dismiss too quickly. It needs no sorted order, no index and no setup, and for a surprising range of real situations that makes it the fastest correct answer, not a beginner's placeholder. This article counts exactly what it costs, and shows where that cost is worth paying.

The problem it solves

You have a collection and a question: is this value in it, and where? The collection might be:

• Unsorted, because items arrive in whatever order they arrive: log lines, form fields, bags on a carousel.
• Small, a dozen settings or a handful of open connections.
• Searched once, so no preparation could ever be repaid.
• Searched by a condition, such as "the first reading above 20 degrees", which no sorted order on the values would answer for you.

Faster searches all demand something up front. Binary search needs sorted data, and a hash set needs to be built. Linear search demands nothing, and in exchange it may have to look at everything.

The intuition

Walk from the front. At each position, compare the item with the target. On a match, stop and return the position; if you fall off the end, report that the target is absent, conventionally with -1.

Three facts follow, and they are the whole analysis:

• Best case: one check, when the target is first.
• Worst case: n checks, when the target is last or missing. A miss always costs the full n, because you cannot know it is absent until you have seen every item. That is the O(n).
• Average for a target that is present, with every position equally likely: (1 + 2 + … + n) / n = (n + 1) / 2 checks. Still O(n), just halved.

It returns the first match. With duplicates, that is a feature: the position you get is the earliest one, which is often exactly what a question means.

Watch it run

The animation searches six coloured items, red, blue, green, teal, gray and pink, for gray. It needs no order and no setup; it just looks at everything until it finds the target. items[0] is red, not gray, so it is ruled out and the pointer steps right. Blue at index 1 and green at index 2 go the same way, and so does teal at index 3, while the checks counter climbs to four and turns to a warning colour. At index 4 the item is gray: a match, returned immediately, without looking at pink. The final frame sums it up: five checks for six items, and a miss would have cost all n. That worst case is the whole story of O(n).

The code

A version that also counts its checks, so the numbers above can be verified rather than trusted. Python's own in and list.index do the same walk in C:

from fractions import Fraction

def linear_search(items, target):
    """Index of the first match, or -1, plus how many items were checked."""
    checks = 0
    for i, item in enumerate(items):
        checks += 1
        if item == target:
            return i, checks
    return -1, checks

bags = ["red", "blue", "green", "teal", "gray", "pink"]
print(linear_search(bags, "gray"))           # (4, 5)
print(linear_search(bags, "plum"))           # (-1, 6)
print("gray" in bags, bags.index("gray"))    # True 4

n = len(bags)
hit = Fraction(sum(linear_search(bags, b)[1] for b in bags), n)
print(hit, Fraction(n + 1, 2))               # 7/2 7/2

Searching for every bag once averages exactly 7/2 checks, the (n + 1) / 2 formula. Searching by a condition is the same loop with a predicate instead of ==. next with a default returns the first match; a comprehension collects all of them:

def first_where(items, pred):
    return next((i for i, x in enumerate(items) if pred(x)), -1)

temps = [12, 15, 9, 22, 31, 18]
print(first_where(temps, lambda t: t > 20))         # 3
print([i for i, t in enumerate(temps) if t > 20])   # [3, 4]

Now the question that matters in practice: when does sorting first pay off? A wrapper class counts every comparison. On 1,000 shuffled values, each linear lookup costs about 464 comparisons; sorting costs 8,652 once, and each binary search after that about 10:

import bisect, random

class Counted:
    calls = 0
    def __init__(self, v):
        self.v = v
    def __lt__(self, other):
        Counted.calls += 1
        return self.v < other.v
    def __eq__(self, other):
        Counted.calls += 1
        return self.v == other.v

rng = random.Random(1)
data = [Counted(v) for v in rng.sample(range(100_000), 1_000)]
queries = [rng.choice(data) for _ in range(40)]

Counted.calls = 0
for q in queries:
    linear_search(data, q)
per_scan = Counted.calls / len(queries)

Counted.calls = 0
ordered = sorted(data)
sort_cost = Counted.calls
for q in queries:
    bisect.bisect_left(ordered, q)
per_bisect = (Counted.calls - sort_cost) / len(queries)
print(round(per_scan), sort_cost, round(per_bisect))   # 464 8652 10
k = 1
while k * per_scan <= sort_cost + k * per_bisect:
    k += 1
print(k)                                               # 20

Below about 20 lookups, scanning wins on comparisons. Above it, sort once and use binary search, or build a set. When some items are asked for far more than others, a list can also organise itself: move each found item to the front, so popular items drift to where the scan starts. Under a skewed workload over 200 names, that cut the average from 85 checks to 47. Last, the seeded check: 2,000 random lists with duplicates, compared against list.index, a brute-force filter for the predicate search, and an invariant for move-to-front:

def move_to_front(items, target):
    i, checks = linear_search(items, target)
    if i > 0:
        items.insert(0, items.pop(i))
    return checks

names = [f"user{i}" for i in range(200)]
weights = [1 / (r + 1) for r in range(200)]
rng.shuffle(names)
popular = sorted(names, key=lambda x: int(x[4:]))
asks = rng.choices(popular, weights=weights, k=20_000)
static = sum(linear_search(names, a)[1] for a in asks)
mtf_list = names[:]
mtf = sum(move_to_front(mtf_list, a) for a in asks)
print(round(static / len(asks)), round(mtf / len(asks)), sorted(mtf_list) == sorted(names))
# 85 47 True

ok = True
for seed in range(2_000):
    r = random.Random(seed)
    xs = [r.randint(0, 9) for _ in range(r.randint(0, 15))]
    t = r.randint(0, 10)
    i, checks = linear_search(xs, t)
    want = xs.index(t) if t in xs else -1
    ok &= i == want and checks == (want + 1 if want >= 0 else len(xs))
    lim = r.randint(0, 10)
    ok &= first_where(xs, lambda x: x > lim) == min([j for j, x in enumerate(xs) if x > lim], default=-1)
    ys = xs[:]
    if t in ys:
        move_to_front(ys, t)
        ok &= ys[0] == t and sorted(ys) == sorted(xs)
print(ok)                                    # True

The complexity

• Time: O(n) worst case and for every miss; (n + 1) / 2 checks on average for a present target at a uniformly random position.
• Space: O(1); it only holds a position.
• Preparation: none, which is the point. Compare O(n log n) to sort before binary search, or O(n) time and memory to build a hash set, both repaid only over many lookups.

The Big-O cheat sheet lists it next to the other searches.

Where it goes wrong

• A scan inside a loop. if x in some_list inside a loop over n items is O(n²) in disguise, the classic hidden quadratic. Convert to a set once. The Python cheat sheet marks x in a and a.index(x) on a list as O(n).
• Forgetting the miss. list.index raises ValueError when the value is absent; check with in, catch it, or use the next(..., -1) form.
• Sorting for one lookup. It costs more comparisons than the scan it replaces.
• Assuming "first" means "only". With duplicates you get the earliest; collect all matches if the question needs them.

When it shows up in interviews

Rarely as a question on its own, and constantly as the baseline. "What's the brute force?" usually means a linear scan, and the follow-up is how to beat it: sort and binary search, or trade memory for a hash set, as in two sum. It also returns in reverse: when the input is unsorted and you need one answer, saying "a single pass is optimal here, any algorithm has to look at every item at least once to prove absence" is a strong answer.

How to say it in an interview

"Linear search checks each item in order and stops at the first match. It needs no sorting or setup, so it works on any collection. The worst case, which includes every miss, is n comparisons, and a present target at a random position averages (n + 1) / 2, so it's O(n) time and O(1) space. I'd use it for small or unsorted data, or a one-off lookup, because sorting first costs O(n log n). For many lookups I'd sort once and binary search, or build a set for O(1) average membership."

Its faster sibling is the next lesson: binary search.