Linear Search

Linear search — also called sequential search or sequential scan — is the simplest possible search algorithm: walk the input one element at a time, comparing each against the target, and return the first index where they match (or a sentinel like -1 if no match). O(n) time worst-case and average-case, O(1) space, no preprocessing, no preconditions on the data. Linear search is the brute-force baseline against which every more sophisticated search algorithm is measured. Despite its triviality it is frequently the right algorithm in practice for: unsorted data (where binary search cannot apply), very small n (where binary search’s overhead dominates), “find any” semantics rather than “find specific” (linear search is naturally adaptive — early exit on first match), streaming data (single-pass with O(1) extra state), and cache-friendly sequential access (which modern CPUs prefetch optimally). Knuth’s TAOCP Vol. 3 §6.1 attributes the sentinel optimization — placing the target at the end of the array to remove the bound-check from the inner loop — to early IBM 7090-era code; in modern compilers vectorization and branch prediction make sentinels mostly obsolete, but the technique remains a textbook illustration of micro-optimization. The branch-prediction implications are the modern subtlety: a successful linear search has a single misprediction at the end (the loop-exit branch), while binary search has O(log n) mispredictions (one per level, fundamentally data-dependent), so on small n linear search’s branch profile can outperform binary search even when the asymptotic comparison count is higher.

1. Intuition — Walking the Aisle

Imagine you’ve lost your keys in your apartment. You walk through each room in some order — kitchen, living room, bedroom, bathroom — looking everywhere as you go. The moment you find the keys, you stop. That is linear search.

There is no clever trick. There is no preprocessing. You don’t sort the rooms first or build an index. You just walk and look. If the keys are in the first room you check, you stop after one room. If the keys are in the last room, you visit every room. If the keys are not in the apartment at all, you visit every room and then conclude they’re not there.

The simplicity is the algorithm’s main virtue. Two consequences:

1. It always works. No precondition. The data can be unsorted, mixed types (in a dynamically-typed language), partially ordered, or arbitrarily structured. As long as you can iterate it and compare for equality, linear search applies.
2. It is “adaptive” — early exit. If the target appears at index k, the algorithm performs exactly k+1 comparisons and stops. Average-case performance on uniform-random target placement is n/2 comparisons; best case is 1; worst case is n.

Compare this to Binary Search, which requires sorted data, and which always performs Θ(log n) comparisons regardless of where the target sits — there’s no early exit because every comparison rules out half the array, not the comparison itself. Linear search wins on best case (O(1) if the target is the first element); binary search wins on worst case (O(log n) vs O(n)).

The intuition for when to use linear search: any time the data is unsorted (and you don’t care to sort it for one query); any time n is small enough that constant factors dominate; any time you need a single-pass sequential algorithm (e.g., over a generator or stream).

2. Tiny Worked Example — Find 7 in [3, 9, 1, 4, 7, 2, 5]

Step through:

Step	i	arr[i]	Compare arr[i] == 7	Action
1	0	3	False	continue
2	1	9	False	continue
3	2	1	False	continue
4	3	4	False	continue
5	4	7	True	return 4

5 comparisons. The target was at index 4; the algorithm performed 5 comparisons (indices 0 through 4). General formula: if the target is at index k, exactly k+1 comparisons; if absent, exactly n comparisons.

Counter-example (target absent): find 8 in the same array. The loop runs all 7 iterations, each comparison fails, the loop falls through and the function returns -1. 7 comparisons.

Best case: find 3 (which is at index 0). 1 comparison. Linear search has no preprocessing cost, so this best case is genuinely O(1) end-to-end — better than binary search even on sorted data (which would do ⌈log₂ 7⌉ = 3 comparisons).

3. Pseudocode

linear_search(arr, target):
    """Returns the smallest index i such that arr[i] == target,
    or -1 if target is not in arr."""
    for i in 0..length(arr) - 1:
        if arr[i] == target:
            return i
    return -1

That is the entire algorithm. There is essentially no design choice; the only variations are: (a) which sentinel value to return when absent (-1, None, raise an exception, etc.), (b) whether to find the first or last match (iterate forward or backward), and (c) whether to stop at the first match or continue and return all match indices.

linear_search_all(arr, target):
    """Returns a list of all indices where target appears."""
    matches := empty list
    for i in 0..length(arr) - 1:
        if arr[i] == target:
            matches.append(i)
    return matches

4. Python Implementation

4.1 Idiomatic Python

def linear_search(arr, target):
    """Return the smallest index i such that arr[i] == target, or -1."""
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

enumerate(arr) yields (index, value) pairs, idiomatic for “I need both.” O(n) time, O(1) extra space (the iterator state).

For the “is the target present at all” question (where the index is irrelevant), Python has the in operator:

present = target in arr        # O(n) for lists, O(1) for sets/dicts

For lists this is internally implemented as a C-level linear search and is much faster than a hand-coded Python for loop because it avoids Python’s per-iteration interpreter overhead. For sets and dicts, in is O(1) average via hashing — but the underlying problem is “membership,” not search, and a different data structure is what gives the speedup.

For finding the index, Python provides list.index(target), which raises ValueError if absent:

try:
    i = arr.index(target)
except ValueError:
    i = -1

4.2 With Sentinel (Pedagogical / Historical)

def linear_search_sentinel(arr, target):
    """Sentinel-based variant: append target to the end so the
    loop never needs to check 'i < n'.
    Mutates arr — use a copy if necessary."""
    n = len(arr)
    arr.append(target)                              # sentinel
    i = 0
    while arr[i] != target:
        i += 1
    arr.pop()                                       # remove sentinel
    return i if i < n else -1

The historical motivation: each iteration of a vanilla linear search performs two comparisons — one against the target (arr[i] == target) and one against the bound (i < n). On 1960s-era hardware (IBM 7090, PDP-7), eliminating one comparison roughly halved the inner-loop cost. Knuth’s TAOCP Vol. 3 §6.1 (1973) discusses this technique extensively.

In modern Python this is slower, not faster, because the append and pop allocations dominate. In compiled C/Rust/Go on small inputs, the sentinel can still produce a small speedup, but modern compilers often hoist or eliminate the bound-check via loop-invariant analysis. The sentinel optimization is largely historical: a textbook illustration of cache-and-cycle-conscious code, not a modern best practice.

4.3 Standard Library Equivalents

Language	Linear search of “find first match”	Notes
Python	arr.index(target) (raises) / target in arr (bool)	Implemented in C
C++	std::find(arr.begin(), arr.end(), target)	Returns iterator
Rust	`arr.iter().position(	&x
Java	Arrays.asList(arr).indexOf(target)	Boxes primitives
Go	Manual loop or slices.Index(arr, target) (Go 1.21+)
JavaScript	arr.indexOf(target)

All of these are linear search on unsorted arrays. None preprocess; all do O(n) worst-case work.

5. Complexity Analysis

Case	Time	Space	Notes
Best case (target at index 0)	O(1)	O(1)	One comparison
Average case (uniform random target placement)	O(n) (precisely (n+1)/2)	O(1)
Worst case (target absent or at last index)	O(n)	O(1)	n comparisons
Preprocessing	None	None

Why average case is (n+1)/2. If the target is equally likely to be at any of the n positions (or absent with some probability q), the expected comparisons are:

E[comparisons | found at i] = i + 1                    (1-indexed: comparisons used)
E[comparisons | absent]     = n
E[comparisons]              = sum_{i=0}^{n-1} (1/n)·(i+1) + 0·n   (assuming always-present)
                            = (1/n) · sum_{i=1}^{n} i
                            = (1/n) · n(n+1)/2
                            = (n+1)/2

For large n, the average is ~n/2. The “factor of 2” speedup vs worst case rarely matters in practice; what matters is the asymptotic Θ(n). This is exactly the result CLRS asks the reader to derive in Exercise 2.2-3 (3rd ed.): assuming the element is present and equally likely to be in any of the n positions, the average number of elements checked is (n+1)/2 ≈ n/2, and the worst case is n (CLRS solutions, Ex. 2.1-3 loop-invariant correctness).

Lower bound for unsorted data. With no preprocessing and no structural assumptions on the array, any algorithm that finds an arbitrary target must in the worst case examine every element — otherwise an adversary could place the target in the unexamined position. So Ω(n) is a tight lower bound for unsorted-array search; linear search achieves this bound. (For sorted data the lower bound drops to Ω(log n), achieved by binary search.)

6. When Linear Beats Binary Search in Practice

The asymptotic comparison O(n) vs O(log n) makes binary search look unconditionally better, but for small n and certain access patterns linear search can win in wall-clock time. The reasons:

6.1 Cache and Prefetching Effects

Modern CPUs prefetch sequential memory accesses aggressively — the L1 prefetcher detects forward strides and pulls cache lines ahead of demand. Linear search’s access pattern is the ideal case: pure forward stride. A linear scan over an array of ints touches 64 / 4 = 16 integers per cache line and the prefetcher loads the next line during the current line’s processing.

Binary search’s access pattern is random — each next access is n/2, n/4, n/8, … away from the previous. None of these accesses prefetch usefully (modern prefetchers can detect patterns up to ~64 lines but binary search’s stride is data-dependent and chaotic). Each binary-search probe for large n is a cache miss, which on modern hardware costs ~100–300 cycles vs ~4 cycles for an L1 hit.

The crossover point depends on hardware and array size; for n up to a few thousand integers, linear search can be faster in practice than binary search despite making more comparisons.

6.2 Branch Prediction

Linear search has one branch (the loop-exit comparison) executed n times. Modern branch predictors handle a tight loop with ~99% accuracy after a few iterations: the predictor learns “always taken” and is wrong only on the final iteration (the misprediction cost is ~10–20 cycles).

Binary search’s branch (if arr[mid] < target vs >=) is fundamentally hard to predict — it depends on the target’s relative position, which is data-driven. Each level of binary search costs roughly 1 misprediction. For n = 1000, binary search has ~10 mispredictions vs linear search’s 1.

This effect is real but dominated by the cache effect on most modern architectures.

6.3 Small n and Constant Factors

For very small n (< ~30 elements), linear search’s tight inner loop (single load, one comparison, branch) is implemented in 3–5 instructions. Binary search has more setup: index computation, mid-computation (lo + (hi - lo) / 2), comparison, branch, update — typically ~10–15 instructions per iteration. The fixed overhead per binary-search iteration multiplied by log n iterations exceeds the linear scan for small n.

C++‘s std::sort and various other library implementations explicitly switch to insertion sort (which is linear scan plus shifts) for small subarrays — typically n < 16 — for exactly this reason. The same threshold applies to “should I binary-search this small array or just scan it?“

6.4 SIMD Vectorization

Modern compilers can auto-vectorize linear search using SIMD instructions: load 8 int32s into a 256-bit register, compare against the target broadcast across all lanes, extract the first match index. Throughput becomes ~8 elements per instruction instead of 1. Binary search cannot vectorize — its access pattern is inherently sequential.

For n up to a few thousand on data that fits in cache, vectorized linear search can outperform binary search by a wide margin.

6.5 “Find Any” vs “Find Specific” Semantics

If the question is “is any element satisfying predicate P present?” rather than “find the index of element x,” linear search is often the right answer — there is no sorted-by-P invariant to exploit. Binary search applies only when the data is sorted in the dimension you’re searching.

6.6 Streaming Data

When the data arrives one element at a time (a generator, a network stream, a file you read line-by-line), random access is impossible — you can only look at the current element and decide whether to keep it. Linear search adapts naturally; binary search cannot apply. (Reservoir-sampling-style algorithms exist for streaming-related problems, but they are not “search” in the classical sense.)

7. The Sentinel Optimization (Historical)

Knuth’s TAOCP Vol. 3 §6.1 (1973) describes the sentinel optimization in detail:

sentinel_search(arr, target, n):
    arr[n] := target            # place sentinel; arr must have allocated slot
    i := 0
    while arr[i] != target:
        i := i + 1
    if i < n:
        return i
    else:
        return -1               # found only the sentinel

The inner loop has only one comparison per iteration (arr[i] != target) instead of two (i < n and arr[i] != target). The sentinel guarantees the loop terminates without checking the bound.

Why it mattered in 1973. On the IBM 7090 (the platform Knuth originally analyzed), each comparison was ~10 cycles. Halving the per-iteration cost halved wall-clock time on linear search, which was a routine bottleneck.

Why it matters less now.

• Modern CPUs can execute the bound-check and the value-check in parallel (out-of-order execution).
• Modern compilers (GCC, LLVM) can hoist the bound-check via loop-invariant code motion or vectorization.
• Modern branch predictors make the bound-check essentially free (it’s mispredicted at most once per loop).
• The sentinel requires mutating the array (or having a pre-allocated extra slot), which has its own costs.

The sentinel pattern still appears in cache-conscious data structures (skip lists with sentinel head/tail nodes, doubly-linked lists with sentinel boundary nodes) where the simplification of edge-case handling justifies the cost.

Uncertain uncertain

Verify: the exact crossover n at which binary search overtakes vectorized linear search on a specific modern microarchitecture (e.g. Intel Golden/Raptor Cove, Apple M-series, AMD Zen 4/5). Reason: this is a hardware-and-data-dependent measurement, not a fact retrievable from a primary spec — published microbenchmarks (e.g. Khuong & Morin’s array-layout work) put it roughly in the low-hundreds-to-low-thousands of elements but it shifts with element width, cache residency, and compiler vectorization. To resolve: benchmark on the target platform. The qualitative effects asserted below — sequential access prefetches well, binary search’s stride is cache-hostile, and binary search incurs ~one branch misprediction per level — are well-established and not in doubt; only the precise crossover is.

8. Variants and Related Algorithms

8.1 Bidirectional Linear Search

Walk from both ends simultaneously: index i from the start, index j from the end, advance both per iteration, return whichever finds a match first. Halves the expected number of iterations on uniformly-distributed targets but doubles the constant per iteration; the trade-off rarely beats vanilla linear search in practice.

8.2 Self-Adjusting / Move-to-Front Heuristic

For workloads with non-uniform target frequency (some queries are repeated more often), maintain the array such that recently-accessed elements move toward the front. After many queries, the array’s order reflects access frequency, and average linear-search cost approaches O(1) for hot items. Used in transposition heuristic (swap with predecessor on hit) and move-to-front (push to position 0 on hit) for self-adjusting lists. See Sleator & Tarjan (1985) “Self-Adjusting Binary Search Trees” for the analogous tree analysis.

8.3 Linear Search with Predicate

Generalizes from “find element equal to target” to “find first element satisfying predicate P.” Same O(n) worst-case; the only change is the comparison. Python’s next(x for x in arr if P(x)) does this idiomatically (returns the first match, raises StopIteration if absent). C++‘s std::find_if is the equivalent.

8.4 Exponential Search

For an unbounded (or very large) sorted sequence with a small target, Exponential Search does O(log k) work where k is the target’s index, by doubling the search range until overshoot then binary-searching. It can be faster than linear search if the data is sorted and the target is far from index 0; otherwise linear search is competitive.

8.5 Binary Search

The natural alternative for sorted data; O(log n) worst-case. See Binary Search for the comparison.

9. Diagram — The Linear Scan

flowchart LR
    Start["arr = [3, 9, 1, 4, 7, 2, 5]<br/>target = 7"]
    Start --> i0["i=0: arr[0]=3<br/>3 != 7"]
    i0 --> i1["i=1: arr[1]=9<br/>9 != 7"]
    i1 --> i2["i=2: arr[2]=1<br/>1 != 7"]
    i2 --> i3["i=3: arr[3]=4<br/>4 != 7"]
    i3 --> i4["i=4: arr[4]=7<br/>7 == 7 ✓"]
    i4 --> Done["return 4"]

What this diagram shows. The linear sweep through the array. Each step examines exactly one element, performs one comparison, and either advances or returns. There is no branching beyond the per-iteration comparison; access is strictly sequential from index 0 onward. This sequential access is what makes linear search optimal for prefetching: each access is at the next cache-line boundary, and the L1 hardware prefetcher predicts and loads the upcoming line during the current line’s processing. The diagram makes visible the algorithm’s lack of cleverness — there is no decomposition, no recursion, no precomputation. The O(n) bound comes for free; getting below it is impossible without preprocessing or structural assumptions on the data.

10. Pitfalls

10.1 Forgetting the “Not Found” Sentinel

The function must explicitly return -1 (or raise, or return None) when the target is absent. Falling off the loop without an explicit return gives undefined behavior in some languages or None in Python (which the caller may misinterpret as “found at index None”). Always have an explicit absent-case return.

10.2 Mutating the Array During Iteration

Iterating with for x in arr and modifying arr mid-iteration produces undefined ordering. If the search is part of a larger workflow that modifies the array, snapshot the array first.

10.3 Equality vs Identity in Object-Comparison Languages

In Python, == invokes __eq__; is checks object identity. For built-in types these usually agree, but for custom classes they can differ. Decide whether you want value-equality (==) or identity (is) and use the right comparison.

10.4 Floating-Point Equality

Linear-searching for a float target with == is fragile: 0.1 + 0.2 != 0.3 in IEEE-754. Use abs(arr[i] - target) < epsilon with a context-appropriate epsilon for floating-point search.

10.5 Searching a Generator Twice

Generators are single-pass: after iterating once, they’re exhausted. target in generator consumes the generator up to the first match (or to the end if absent), and the generator cannot be re-iterated. Convert to a list (list(gen)) if you need multiple searches.

10.6 The Bound-Check Bug When Hand-Rolling Sentinel Search

The sentinel form (§4.2) requires the array to have an allocated slot at index n (the end). Naively arr[n] = target on a length-n array raises IndexError in Python (and is undefined behavior in C if the slot is not allocated). The Python implementation uses append/pop to handle this; in C, allocate n+1 slots up front.

10.7 Off-by-One in the Loop Bound

for i in range(len(arr)) iterates 0..n-1 (inclusive); for i in range(len(arr) - 1) iterates 0..n-2, missing the last element. Double-check the loop bound; off-by-ones in linear search are silent (no out-of-bounds error, just a missing comparison).

10.8 Choosing Linear Search for Sorted Data

If the data is sorted and you’ll do many queries, binary search is asymptotically better. The mistake is using linear search on a sorted array out of habit. Conversely: if you’ll do one query and the data is unsorted, don’t sort it first to enable binary search — sorting is O(n log n), more expensive than the linear scan it would enable.

10.9 Misapplying the Sentinel Optimization

The sentinel optimization mutates the array (writing to arr[n]). In a multi-threaded context, this is a data race; in a memory-mapped or read-only buffer, it segfaults. Many “optimization” attempts have introduced subtle bugs by adding a sentinel without considering ownership. In modern compiled code the optimization rarely buys anything anyway.

10.10 Confusing “Linear” with “Brute Force”

Linear search is linear time but not always brute force in spirit. “Linear search with self-adjusting heuristic” is O(n) worst-case but O(1) expected on hot items — a genuinely sophisticated structure. The simplicity of the algorithm doesn’t preclude clever uses of it.

11. Common Interview Problems

Problem	LeetCode #	Pattern
Find the Index of the First Occurrence	LC 28	Linear search of substring (or KMP for O(n+m)); naive is O(nm)
Two Sum (unsorted, brute force)	LC 1	Nested linear searches, O(n²) brute force; hash table gives O(n)
Find First Element Satisfying Predicate	Folklore	Direct linear search with predicate
Linear search in linked list	Classical	O(n) traversal of Linked List Cycle Detection’s linked list — no random access; binary search not applicable
Find majority element (Boyer-Moore)	LC 169	O(n) linear scan with cleverness; not technically “linear search” but in the same algorithmic family
Maximum element	Classical	One-pass linear scan tracking the running max
Minimum / count / sum / etc.	Classical	Generalizations of linear search to “linear reduce”

The interview gotcha is recognizing when the problem permits binary search and when it doesn’t. If the data is unsorted and a single query is asked, linear search is the right answer and proposing binary search (which would require sorting first) is wrong.

12. Open Questions

• What is the precise crossover n between vectorized linear search and binary search on modern x86_64 (with AVX-512)? Empirical measurements from various sources put it in the range n ∈ [16, 1000] depending on element size and cache state. Verify against current benchmarks.
• Are there theoretically-improved variants of linear search beyond the sentinel optimization? The Bentley–Yao 1976 paper has lower-bound results suggesting linear search is comparison-count-optimal for unsorted data; verify.
• In a streaming model where elements arrive over time and queries arrive interleaved, what is the optimal data structure that supports “linear search” queries with bounded latency? (This generalizes to streaming algorithms; outside the scope of pure linear search.)

13. See Also

• Binary Search — O(log n) alternative for sorted data; the natural successor when the array can be sorted
• Interpolation Search — O(log log n) for uniform-distributed sorted data; rarely used in practice
• Exponential Search — O(log k) for unbounded sorted sequences with a small-index target
• Hash Table — O(1) average membership test; the right answer when you can preprocess and only need yes/no
• Big-O Notation — for the O(n) worst-case bound and the Ω(n) lower bound for unsorted-array search
• Two Pointers — generalizes linear scanning with multiple cursors
• Sliding Window — another single-pass linear technique
• SWE Interview Preparation MOC