Linear Search

Linear search examines elements in sequence until it finds a match or exhausts the input. It works on unsorted data and on iterables without random access.

from collections.abc import Iterable
from typing import TypeVar

T = TypeVar("T")


def linear_search(values: Iterable[T], target: T) -> int | None:
    for index, value in enumerate(values):
        if value == target:
            return index
    return None

Returning None separates “not found” from valid index values without relying on a negative sentinel.

Invariant

Before inspecting position $i$, the target does not occur in the already checked prefix. If equality is found, the algorithm returns the first matching position.

Cost

• Best case: $O(1)$.
• Worst case: $O(n)$ comparisons.
• Auxiliary space: $O(1)$ for an iterative implementation.

An “average of half the elements” claim requires a probability model for target presence and position; $O(n)$ is the robust average-order statement.

Use boundary

Use linear search for small data, a one-off query, streaming input, or a predicate that cannot exploit stronger structure. For repeated queries, consider whether sorting, indexing, or hashing amortizes its construction cost.

A probability model and boundary cases

For [4, 7, 7] and target 7, comparison 4 == 7 fails and 7 == 7 succeeds: return index 1 after two comparisons, not the last occurrence 2. An absent target costs three comparisons; empty input returns None immediately. A finite input terminates because each iteration consumes another element. An infinite iterable with no matching element need not terminate; searching an iterator also consumes its elements through the match or exhaustion.

If the target is present exactly once and its position is uniform among $n$ positions, expected comparisons are $(1+2+\cdots+n)/n=(n+1)/2$. If it is present with probability $p$ under that same conditional model, the expectation becomes $p(n+1)/2+(1-p)n$. A target always at the first position instead gives constant cost. All these counts assume constant-time equality and iteration; comparing long strings or generating stream elements may cost more.

Run these boundary checks after the definitions above:

assert linear_search([], 7) is None
assert linear_search([7], 7) == 0
assert linear_search([4, 7, 7], 7) == 1
assert linear_search([4, 7], 9) is None
stream = iter([4, 7, 9])
assert linear_search(stream, 7) == 1
assert next(stream) == 9

Source

• Open Data Structures

My reading · Opened notes are remembered in this browser.