Linear search: the honest baseline

Chapter 1 — Find one SKU in an unsorted flash-sale list

Imagine a midnight drop: product rows arrive in whatever order the warehouse scanned them. A shopper asks, “Is SKU 4418 still in stock?” Your job is to scan the list until you find that ID or prove it is not there. That honest scan is linear search — the baseline every faster algorithm in this track will be judged against.

A minimal, correct implementation

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

Two things matter here. First, the loop variant: every iteration, we either return (we found the answer) or we move on to the next index. Second, the contract on the return value: we distinguish "not found" (-1) from a real index. Breaking either of those promises is how search bugs move into production.

What does this really cost?

If a has n elements, linear search performs up to n comparisons in the worst case (the target is at the end, or not present at all). On average, for a uniformly random target that is in the array, it performs about n/2 comparisons. Both of those are O(n) — the work grows in proportion to the size of the input.

When linear search is the right tool

• The array is small — the constant factors of anything fancier dominate.
• The data is unsorted and you will only search once — the cost of sorting first exceeds a single scan.
• You do not have random access (linked list, stream) — indexing into the middle is not cheap anyway.
• You care about simplicity and a human reader has to verify the code.

An invariant worth naming

Every loop has an invariant — a sentence that is true before and after each iteration. For linear search the invariant is: after iteration i, I have checked indices 0…i and the target was not among them. When the loop exits without returning, the invariant tells you the target is not in the array at all. Training yourself to state loop invariants in plain English is half the battle with every algorithm in this course.

Interactive — feel the baseline

Open the visualization playground, stay on linear search, and drag the problem size. Notice how comparisons scale one-for-one with list length — that is the cost this chapter names.

Full playground — switch mode to Linear and step through →