Linear Search

Overview

Linear search, also known as sequential search, is the simplest searching algorithm. It sequentially checks each element in a list until it finds the target value or reaches the end of the list.

Despite its simplicity, linear search is fundamental and widely used, especially when data is unsorted or when working with small datasets where the overhead of more complex algorithms isn't justified.

It is easy to dismiss linear search as the toy algorithm you should stop using as soon as you learn binary search. That would be a mistake. Linear search is optimal in more situations than people realise, and it is running under the hood in more of your code than you probably think: every time you use Python's in operator on a list, C++'s std::find, or JavaScript's Array.prototype.includes, you are calling linear search. And on modern hardware with SIMD instructions, it can process 8 or 16 elements per cycle, making it competitive with more sophisticated algorithms on surprisingly large arrays.

When Linear Search Is Actually Optimal

There is a family of problems where no algorithm can beat linear search, not asymptotically, not by constant factors, not with clever data structures. Understanding when you are in that regime is one of the more useful pieces of algorithmic judgement.

Unsorted data with a single search. If the data is not sorted and you plan to search it exactly once, you cannot do better than O(n), sorting the data first would take Ω(n log n), which is strictly worse than the linear scan you were trying to avoid. This is why linear search is the correct algorithm for one-off queries against a stream of log lines, a batch of unindexed database rows, or the contents of a small in-memory cache.

Very small arrays. The O(n) versus O(log n) comparison is asymptotic. At small n, linear search has better cache behaviour than binary search, sequential reads that the CPU prefetcher can predict perfectly, and its branch predictor behaviour is more uniform. On typical x86 hardware, linear search beats binary search up to somewhere between 16 and 128 elements, depending on element size. The Bentley–McIlroy "Engineering a Sort Function" paper (1993) discusses this crossover in detail and it is the reason production sorts fall back to insertion sort (which uses linear search internally) on small subarrays.

When the target is expected near the front. On non-uniform search distributions where the target is likely to appear early, a most-recently-used list, a self-organising list that moves accessed elements toward the front, linear search finds the target in an average of O(1) or O(log n) rather than O(n/2). No other algorithm exploits this structure automatically.

Streaming or online data. When data arrives one element at a time and you want to check each new arrival, linear search is not just optimal but the only algorithm that works, sorted-data algorithms require the full input up front.

Very small key types where SIMD applies. A modern CPU with AVX-512 can compare 64 bytes of memory in a single instruction. Searching a byte array of a few thousand elements this way is often faster than any tree- or hash-based lookup because the hardware pipeline stays saturated. This is exactly how memchr in glibc and similar functions in Rust's standard library are implemented.

Optimisations Worth Knowing

Sentinel-Based Linear Search

The plain implementation has a bounds check on every iteration: while i < len(arr) and arr[i] != target. The bounds check pays for nothing, it is there only to keep us from running off the end of the array. A classic optimisation places a copy of the target at the end of the array as a sentinel, and then loops on just while arr[i] != target. The sentinel guarantees we will eventually match, so the bounds check becomes unnecessary. After the loop, we check whether the match index is less than the original length, if not, the target was not in the original array.

def linear_search_sentinel(arr, target):
    arr.append(target)             # sentinel
    i = 0
    while arr[i] != target:
        i += 1
    arr.pop()                      # remove sentinel
    return i if i < len(arr) else -1

This is roughly 30–50% faster than the naive version in a tight loop, because modern CPUs can pipeline a single-condition loop much better than a two-condition loop. In Python the overhead of the append/pop wipes out the gain, but in C or Rust the trick is genuinely worth it.

Move-to-Front Heuristic

Also called the "self-organising list" strategy. When you find an element by linear search, move it to the front of the list. Frequently-accessed elements end up near the front and are found in near-constant time. This has beautiful theoretical properties, Sleator and Tarjan proved in 1985 that move-to-front is within a factor of 2 of the optimal static ordering, without needing to know the access frequencies in advance. It is used in some cache eviction policies and in the LZ77 family of data compression algorithms.

SIMD / Vectorised Search

Modern CPUs offer instructions that compare multiple values in parallel. AVX2 can compare 32 bytes at once; AVX-512 can compare 64. Vectorised linear search reads the array in 16- or 32-element chunks, compares all elements against the target in a single instruction, and uses a bitmask + trailing-zero-count to find which element (if any) matched. This turns linear search into an O(n/16) algorithm with a very small constant, often beating binary search up to arrays in the tens of thousands. Rust's iter::position and C++'s std::find use this technique on integer types where it is safe.

Interpolation Search

A generalisation that works on sorted data with uniform distribution: instead of always looking at the middle (as binary search does), estimate where the target should be based on its value's position between the endpoints. This is how you would search a phone book, "Smith" is near the end, not the middle. Interpolation search runs in O(log log n) on uniformly-distributed data, which is asymptotically faster than binary search. On non-uniform data it degrades to O(n), so it is used only when the distribution is known.

Common Misconceptions

• "Linear search should never be used on sorted arrays." If you are going to search only once and the array is small (say, under 32 elements), a linear scan is often faster than binary search, better cache behaviour and no branch mispredictions.
• "Linear search takes n/2 comparisons on average." Only if the target is present and uniformly likely to appear anywhere. If the target is often absent, every search takes n comparisons. If the target follows a skewed distribution, move-to-front makes the average much better than n/2.
• "Linear search is not used in production code." It is used everywhere: hash-table collision chains (short chains are searched linearly), small enum lookups in compilers, dispatch tables in interpreters, cache lookups, memchr, strchr, std::find. It is one of the most-called functions in most large codebases, usually implicitly.

How It Works

The algorithm works by:

1. Starting from the first element of the array
2. Comparing each element with the target value
3. If a match is found, returning the index
4. If the end is reached without finding a match, returning -1 (or indicating not found)

Algorithm

LinearSearch(arr, target):
    for i = 0 to arr.length - 1:
        if arr[i] == target:
            return i
    return -1  # Target not found
                

Implementation

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1
                

Complexity Analysis

• Time Complexity:
  • Best Case: O(1) - Target found at the first position
  • Average Case: O(n), about n/2 comparisons when the target is present and equally likely to be anywhere, and n when it is absent. Note that O(n/2) and O(n) are the same set, so the correct relation is "=", not "≈", constant factors vanish inside big-O.
  • Worst Case: O(n) - Target not found or at the last position
• Space Complexity: O(1) - Only using a constant amount of extra space

Characteristics

• Simple: Easy to understand and implement
• No Prerequisites: Works on any data structure (arrays, lists, etc.)
• No Sorting Required: Works on unsorted data
• Inefficient for Large Data: Must check every element in worst case

One practical note that cuts against the theory: for small arrays linear search often beats binary search despite the worse complexity. It reads memory sequentially, which the cache and prefetcher handle perfectly, and it has no unpredictable branches; binary search jumps around and mispredicts on nearly every comparison. The crossover is typically somewhere around 32–128 elements depending on element size. This is the same reason production sorts fall back to insertion sort on small subarrays.

When to Use Linear Search

Linear search is appropriate when:

• Data is unsorted and sorting would be more expensive than searching
• Working with small datasets where O(n) is acceptable
• Data is frequently changing, making it impractical to maintain sorted order
• Simplicity is more important than performance
• Searching through linked lists or other sequential data structures

Example

Searching for 7 in [3, 1, 7, 9, 2, 5]:

Step 1: Check arr[0] = 3, not equal to 7
Step 2: Check arr[1] = 1, not equal to 7
Step 3: Check arr[2] = 7, found! Return index 2
                

Related Algorithms

Explore other searching algorithms:

• Binary Search - Efficient O(log n) search for sorted data
• Back to Searching Algorithms Overview