---
title: 'Linear Search'
source: 'https://academia.sh/en/courses/algorithms/linear-search'
course: Algorithms
language: en
updated: '2026-08-17T18:07:42+00:00'
license: 'CC BY-SA 4.0'
---

# Linear Search

Scanning unordered data, the expected comparison count for successful and unsuccessful search, the sentinel, and the justification of the linear lower bound.

The analysis tools are ready; this topic applies them for the first time to a family
of algorithms. Searching and sorting form suitable ground for this work, because they
lend themselves to placing side by side solutions to the same problem at different
costs.

The simplest search is the starting point: walking the elements from start to end.

## The Algorithm and Its Correctness

**Linear search** scans the array from start to end and returns the first position
where it finds the sought value.

```python
def linear_search(array: list[int], target: int) -> int:
    """The target's first position; -1 if not found.

    Invariant: at the start of every iteration, the target is not in the range 0..i-1.
    Termination: the number of remaining elements decreases by one every iteration.
    """
    for i in range(len(array)):
        if array[i] == target:
            return i
    return -1


measurements = [5, 2, 9, 1, 5, 6]
print(linear_search(measurements, 9))     # 2
print(linear_search(measurements, 5))     # 0   — first match
print(linear_search(measurements, 7))     # -1
```

Correctness is given by the two sentences in the docstring. The loop invariant, once
the loop ends, becomes "the target is not in the range 0..n-1"; this justifies
returning `-1`. The decreasing quantity is the termination guarantee.

Two design decisions are made implicitly: if there are equal values, the **first**
position is returned, and not-found is reported with a value that cannot be a valid
index.

## The Cost of the Three Cases

The measure is the number of comparisons.

**Best case:** The target is the first element; 1 comparison, $O(1)$.

**Worst case:** The target is the last element, or does not exist at all; $n$
comparisons, $O(n)$.

**Average case:** Assuming the target is present in the array and every position is
equally likely, the expected number of comparisons is

$$
\frac{1 + 2 + \dots + n}{n} = \frac{n+1}{2}
$$

which is also $O(n)$. In an unsuccessful search, $n$ comparisons are always made.

```python
def comparison_count(array: list[int], target: int) -> int:
    for i in range(len(array)):
        if array[i] == target:
            return i + 1
    return len(array)


array = list(range(100))
total = sum(comparison_count(array, h) for h in array)
print(total / len(array))                    # 50.5   — (n+1)/2
print(comparison_count(array, -1))           # 100    — unsuccessful search
```

The average is roughly half the worst case. A constant-factor difference does not
change the asymptotic class: both cases are linear. This shows when average-case
analysis is meaningful — it determines the constant, not the class.

## The Sentinel

The loop performs two tests every iteration: has the index bound been exceeded, and
does the element equal the target. If the target is temporarily appended to the end
of the array, the bound test becomes unnecessary; the search stops at that element at
the latest.

```python
def sentinel_search(array: list[int], target: int) -> int:
    array.append(target)               # sentinel
    i = 0
    while array[i] != target:
        i += 1
    array.pop()
    return i if i < len(array) else -1


data = [5, 2, 9, 1, 5, 6]
print(sentinel_search(data, 9), sentinel_search(data, 7), data)   # 2 -1 [5, 2, 9, 1, 5, 6]
```

The gain is in the constant factor; the class is still $O(n)$. The method's cost is
that it temporarily modifies the array — it cannot be used on shared data or in a
multithreaded environment.

This is a recurring lesson of the course: constant-factor improvements are real, but
they do not substitute for an idea that changes the class.

## Why Nothing Better Is Possible

The cost of search in an unordered array cannot be reduced, and the justification for
this is an **adversary argument**.

Suppose an algorithm does not look at all $n$ elements. There is at least one
position it did not look at. When the algorithm says "not found", the adversary
places the target at that position; since the algorithm's observations have not
changed, neither does its answer, but the answer is now wrong.

So every algorithm that works correctly must, in the worst case, look at every
element: search in unordered data is $\Omega(n)$. Because linear search reaches this
bound, it is **optimal** without any assumption of order.

The only way to escape this bound is to change the assumption: keep the data sorted,
or build an index structure. The next lesson follows the first route; the hash table
from the Data Structures course follows the second.

## Access Distribution and the Effect of Ordering

The average-case calculation assumed every element is searched for with equal
probability. Real accesses are often not evenly distributed: a few records are
searched for frequently, the rest rarely.

With the probability of element $i$ being searched for equal to $p_i$, the expected
number of comparisons is

$$
\sum_{i=1}^{n} i \cdot p_i
$$

This expression reaches its smallest value when the elements are arranged in
**decreasing order of probability**. In other words, the array's order determines the
cost, and the best static arrangement is ordering by frequency.

```python
def expected_cost(probabilities: list[float]) -> float:
    return sum((i + 1) * p for i, p in enumerate(probabilities))


print(round(expected_cost([0.1, 0.2, 0.7]), 2))      # 2.6   — bad ordering
print(round(expected_cost([0.7, 0.2, 0.1]), 2))      # 1.4   — ordered by frequency
```

If frequencies are not known in advance, heuristics that reorganize the list at run
time are used: the found element is moved to the front, or advanced by one position.
These do not change the worst case — the class is still $O(n)$ — but they noticeably
lower the average under skewed distributions.

## Multiple Pieces of Information in One Pass

A linear scan does not have to search only for a match; several quantities can be
collected in the same pass. Searching for the minimum and the maximum separately
requires $2n$ comparisons; processing elements two at a time lowers the cost.

```python
def min_and_max(array: list[int]) -> tuple[int, int, int]:
    """Returns (minimum, maximum, comparison count)."""
    n = len(array)
    if n % 2 == 0:
        low, high = min(array[0], array[1]), max(array[0], array[1])
        i, count = 2, 1
    else:
        low = high = array[0]
        i, count = 1, 0

    while i < n - 1:
        a, b = array[i], array[i + 1]
        if a > b:
            a, b = b, a
        count += 3                       # within-pair comparison + comparison with both ends
        low = min(low, a)
        high = max(high, b)
        i += 2
    return low, high, count


print(min_and_max([5, 2, 9, 1, 5, 6]))          # (1, 9, 7)
print(min_and_max(list(range(100))))            # (0, 99, 148)
```

For a hundred elements, 148 comparisons are made; searching separately would require
198. The general formula is $3n/2 - 2$, and this is the known lower bound for the two
extremes.

The class is still $O(n)$. The gain matters when data comes from disk or the network
and every pass is expensive: any information that can be collected in one pass is
cheaper than a second pass.

## Summary

- Linear search works on unordered data; its correctness is justified by the loop
  invariant and the decreasing quantity.
- The best case is constant, the worst case is linear; the expected cost of a
  successful search is $(n+1)/2$ comparisons.
- The sentinel removes the bound test; the gain is a constant factor, the class does
  not change.
- The adversary argument shows that search in unordered data is $\Omega(n)$; linear
  search reaches this bound.
- If access probabilities are not equal, ordering elements by decreasing frequency
  lowers the expected cost.
- Collecting more than one quantity in a single pass reduces the number of passes and
  the total comparisons.

## Next Step

The way to escape the linear lower bound is to build an assumption on the data. If
the data is sorted, every comparison eliminates not just one element but half of
them. The next lesson covers this idea — binary search — and the boundary conditions
that are surprisingly difficult to write correctly.