= Linear search
{wiki}
= Sequential search
{synonym}
<Linear search>, also called <sequential search>, examines a finite <sequence> from its beginning, performing an <equality test> on each entry until one matches the target or the entries run out. It needs no <sorted array> or <total order> on the values. This makes it useful for a small collection, a one-off lookup, or data available only in succession: the next entry is enough to make progress.
Specify the answer precisely. For an <array> $A$ of length $n\geq0$ with indices $0,\ldots,n-1$ and target $x$, return the smallest index $j$ satisfying $A_j=x$, or a distinct absent result if no such index exists. Repeated values are allowed. In this contract, finding a later duplicate is insufficient when an earlier match exists. Assume the <input> remains unchanged during the search and each <equality test> terminates with a stable truth value expressing the intended matching relation.
Here is an implementation in <Python>; `None` represents absence and is distinct from the valid index zero:
``
def linear_search(entries, target):
for index, entry in enumerate(entries):
if entry == target:
return index
return None
``
The official <Python> <sequence> method `s.index(x)` likewise specifies the first occurrence, but signals absence by raising `ValueError`. An API's absent-result convention belongs to its contract.<Python 3.14 documentation/Built-in Types, Python 3.14 documentation>[Python 3.14 documentation, Common Sequence Operations: s.index(x), first occurrence and ValueError]{ref}
Take the original unsorted <array> $A=[7,4,7,2,9]$. For $x=7$, the first <equality test> succeeds and returns index $0$; the other $7$ at index $2$ is never inspected. For $x=2$, the checks against $7,4,7$ fail, the check against $2$ succeeds, and the answer is index $3$ after four <equality tests>. For absent target $x=6$, all five <equality tests> fail and the answer is `None`. On the empty <sequence>, there is no entry to inspect: return `None` with zero <equality tests>.
\Image[/linear-search-unsorted-array-trace.png]
{title=<Linear search> on an unsorted <array>: first duplicate, later match, and absent target}
{description=Indices start at zero. Each numbered cell is one <equality test>; green cells match, orange cells fail, and grey cells are never inspected. The empty <sequence> requires zero <equality tests>.}
Value order never justifies skipping an entry in this <algorithm>. For $x=2$, stopping because the first value $7$ is larger would give a wrong absent result. Any <permutation> of the <input> remains searchable by <linear search>, although the first matching index and number of <equality tests> can change. By contrast, <binary search> uses a <total order> and the <sorted array> property to discard whole candidate ranges. Its logarithmic <time complexity> additionally assumes cheap access to middle entries; a sorted <linked list> does not acquire constant-cost indexed access merely by being sorted. Sorting for a single query also has a cost, and changes positions relative to the original <sequence>.
Back to article page
