Skip to main content

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 ii, 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)O(1).
  • Worst case: O(n)O(n) comparisons.
  • Auxiliary space: O(1)O(1) for an iterative implementation.

An “average of half the elements” claim requires a probability model for target presence and position; O(n)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.

Source​