Linear Search

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.

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.

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.

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.

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.

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.