Linear Search¶

Linear search inspects elements from left to right until it finds the target or exhausts the sequence. It requires no ordering.

Contract¶

Input: an integer array and a target.
Output: the smallest index containing the target, or -1 when absent.
The array is not modified.

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

Correctness¶

At the start of iteration i, no index in [0, i) contains the target. If values[i] matches, i is therefore the first matching index. Otherwise, the invariant extends to [0, i + 1). If the loop ends, every valid index has been excluded, so returning -1 is correct.

Complexity¶

best case: Θ(1) when the first element matches;
worst case: Θ(n) when the target is absent or last;
auxiliary space: Θ(1).

Exercises¶

Return every matching index instead of the first.
Generalize the method using List<T> and Objects.equals.
Explain when linear search is preferable to sorting and binary search.