Linear Search

1Introduction

This lecture explains the procedure, correctness, and complexity of linear search, which compares array elements in order from the beginning. For an arbitrary array, when the algorithm uses only equality comparisons and assumes neither sorted order nor an auxiliary lookup structure, a comparison with one element cannot eliminate other elements collectively. Each element must therefore be examined individually.

2Problem statement and terminology

Let

be an array of length $$n$$n, and let $$x$$x be a target value. If some index $$i$$i satisfies $$A_i=x$$A_i=x, the algorithm returns the smallest such index. If no such index exists, it reports failure.

Linear search compares $$A_0,A_1,\dots ,A_{n-1}$$A_0,A_1,\ldots,A_{n-1} with the target in this order and terminates at the first match. The number of comparisons is the number of evaluations of the equality $$A_i=x$$A_i=x.

3Procedure

For $$i=0,1,\dots ,n-1$$i=0,1,\ldots,n-1 in order, perform the following steps.

1. Evaluate $$A_i=x$$A_i=x.
2. If the equality holds, return $$i$$i and terminate.
3. Otherwise, proceed to the next index.

If no index produces a match, report failure. This procedure does not depend on whether the array is sorted.

4Correctness by a loop invariant

A loop invariantLoop invariant is a proposition that holds at a designated point of every iteration. Immediately before the comparison at index $$i$$i, use the invariant

4.1Initialization

Immediately before the first comparison, $$i=0$$i=0. No element has been compared, so the invariant holds over the empty set of preceding indices.

4.2Maintenance

Assume that the invariant holds immediately before the comparison at index $$i$$i. If $$A_i=x$$A_i=x, no smaller index contains a match, so $$i$$i is the smallest index satisfying the specification. If $$A_i\ne x$$A_i\ne x, none of $$A_0,\dots ,A_i$$A_0,\ldots,A_i equals $$x$$x. The invariant therefore holds immediately before the comparison at index $$i+1$$i+1.

4.3Termination

If the algorithm terminates at a match, the maintenance argument shows that the returned index is the first matching position. If it reaches $$i=n$$i=n without a match, the invariant shows that none of $$A_0,\dots ,A_{n-1}$$A_0,\ldots,A_{n-1} equals $$x$$x. Reporting failure is therefore correct.

Initialization, maintenance, and termination together prove that linear search satisfies its specification.

5Complexity

Assume $$n>0$$n>0. In the best case, the target equals the first element $$A_0$$A_0. The algorithm performs one comparison, so its best-case running time is $$\mathrm{\Theta }\left(1\right)$$\Theta(1).

If the target occurs only at the final element or does not occur in the array, the algorithm performs $$n$$n comparisons. Its worst-case running time is therefore $$\mathrm{\Theta }\left(n\right)$$\Theta(n). Apart from its index and return value, it uses no storage proportional to the input length, so its auxiliary-space complexity is $$\mathrm{\Theta }\left(1\right)$$\Theta(1).

When $$n=0$$n=0, the algorithm performs no comparisons and reports failure immediately.

6Applicability and connection to binary search

Linear search requires only sequential access to elements and equality comparison; it does not require sorted order. In a sorted array, however, order information can eliminate multiple candidates at once. The next lecture explains binary search, which uses this property.

7Summary

• Linear search compares array elements with the target in order from the beginning.
• Initialization, maintenance, and termination of the loop invariant prove that the algorithm correctly returns the first matching position or reports failure.
• Its best-case running time is $$\mathrm{\Theta }\left(1\right)$$\Theta(1), its worst-case running time is $$\mathrm{\Theta }\left(n\right)$$\Theta(n), and its auxiliary-space complexity is $$\mathrm{\Theta }\left(1\right)$$\Theta(1).