1. Linear Search

Linear search — also called sequential search — is the simplest algorithm for locating a target element in a collection: it inspects each element in turn until a match is found or all elements are exhausted. No preconditions are imposed on the collection; it need not be sorted, contiguous in memory, or even finite in advance. Knuth ¹ treats it as the baseline against which every faster search method must justify its additional requirements.

Despite its \(O(n)\) worst-case cost, linear search is often the correct choice in practice: for small or unsorted arrays, for linked lists (which do not support \(O(1)\) random access needed by binary search), and as the inner loop of algorithms that search very short sublists.

1.1 Problem Statement

Given a sequence \(A = \langle a_0, a_1, \ldots, a_{n-1} \rangle\) of \(n\) elements drawn from a totally ordered set, and a target value \(t\), find the smallest index \(i\) such that \(a_i = t\), or report that no such index exists.

1.2 The Algorithm

The procedure is direct: maintain a cursor \(i\) starting at 0, compare \(a_i\) with \(t\), advance if they differ, and halt when they match or the array ends.

LINEARSEARCH(A, n, t):
  for i = 0 to n - 1:
    if A[i] = t:
      return i
  return ⊥

1.2.1 Loop Invariant

At the start of each iteration with cursor value \(i\):

\(t \notin \{a_0, a_1, \ldots, a_{i-1}\}\)

That is, the target has not been found in any position before \(i\). On termination either the invariant is broken by a match at position \(i\) (return \(i\)), or \(i\) reaches \(n\) with the invariant still holding, confirming absence (return \(\bot\)).

1.3 Complexity Analysis

1.3.1 Comparisons

Let \(C(n)\) denote the number of element–target comparisons.

Best case (\(t = a_0\)): the first comparison succeeds.

Worst case (\(t \notin A\) or \(t = a_{n-1}\)): every element is inspected.

Average case (uniform distribution over positions, \(t\) present with probability \(p\)):

The expected number of comparisons when \(t\) is at position \(j\) (uniformly distributed over \(\{0, \ldots, n-1\}\)) is:

When \(t\) is always present (\(p = 1\)): \(C_{\text{avg}} = (n+1)/2\). When \(t\) is never present (\(p = 0\)): \(C_{\text{avg}} = n\).

1.3.2 Summary

Linear search is in-place (\(O(1)\) extra space) and does not require preprocessing.

1.4 Optimality

For an unsorted collection with no additional data structure, linear search is information-theoretically optimal: every element must be a candidate until proven otherwise, so any algorithm must in the worst case inspect all \(n\) elements. This follows from an adversary argument: for any deterministic algorithm that halts before inspecting all elements, the adversary can place \(t\) in the last unexamined position.

For a sorted collection, binary search achieves \(O(\log n)\) and is strictly superior for large \(n\) (see Binary Search).

1.5 Variants

1.5.1 Sentinel Search

A sentinel is a copy of \(t\) placed at position \(A[n]\) (a temporary extension of the array) before the scan. This eliminates the bounds check i < n from every iteration, replacing two comparisons per step with one:

SENTINELSEARCH(A, n, t):
  A[n] = t          // write sentinel
  i = 0
  while A[i] ≠ t:
    i = i + 1
  if i < n:
    return i
  return ⊥

The sentinel guarantees the loop terminates without an explicit bounds check. The savings are constant-factor only but matter in tight inner loops on large arrays.

1.5.2 Self-Organising Search (Move-to-Front)

If elements are searched repeatedly with non-uniform probabilities, moving each found element to the front of the list after each access reduces the expected search length over time. Under the independent reference model, the move-to-front heuristic achieves expected search length that is at most twice optimal for any fixed probability distribution ¹.

1.5.3 Transposition Search

A weaker variant: swap the found element with its predecessor rather than moving it to the front. This adapts more slowly but causes less disruption for distributions where one element does not dominate all searches.

1.5.4 Ordered Linear Search

When \(A\) is sorted, comparing \(a_i > t\) (rather than just \(a_i \neq t\)) allows early termination on failure: once an element exceeding \(t\) is encountered, all subsequent elements also exceed \(t\), so \(t\) cannot be present. This reduces the average unsuccessful search cost from \(n\) comparisons to \(\approx n/2\).

1.6 Comparison with Binary Search

The crossover point — where the preprocessing cost of sorting amortises over many binary searches — is \(k \approx n \log_2 n / \log_2 n = n\) searches (ignoring constants). For fewer than \(n\) total searches on an unsorted array, linear search is cheaper overall.

1.7 Applications

• Small arrays (\(n \lesssim 8\)): the constant overhead of binary search (index arithmetic, bounds checks) makes linear search faster in practice.
• Linked structures: traversal is inherently sequential, so \(O(1)\) random access required by binary search is unavailable.
• Streaming data: elements arrive one at a time with no prior knowledge of the sorted order; search must be done as data is ingested.
• Last-element searching: variants such as find_last_of in C++ or rfind scan right to left.
• Inner loop of algorithms: e.g. insertion sort's inner scan to find the insertion position, or linear-time bucket search.

1.8 Interactive Demo

The animation below shows linear search on a 16-element array. Click Present to search for a target that exists, or Absent to search for one that does not (triggering a full scan).