Linear search is a search algorithm that examines the elements of a collection one at a time until it finds an element satisfying a specified condition or determines that no such element exists. It requires no sorting or search index and works with many kinds of data structures, including arrays and linked lists. For a collection of elements, its worst-case running time is proportional to , assuming that accessing and testing each element takes constant time.
Basic procedure
In its simplest form, linear search looks for a target value by comparing it with each element in sequence. A search that begins at the start of a collection and stops at the first match returns the earliest matching position. Other versions return the matching element itself, a Boolean result, or all matching positions.
The following pseudocode searches a zero-indexed array:
linear_search(A, target):
for i = 0 to length(A) - 1:
if A[i] == target:
return i
return NOT_FOUND
For the array [14, 7, 23, 7, 9], searching for 7 examines 14 and then 7, returning index 1. Searching for 5 examines every element before returning NOT_FOUND. An empty array requires no element comparisons.
Equality is not essential to the method. A linear search can instead test a predicate, such as whether a record has a specified identifier or whether a measurement exceeds a threshold. The cost of that predicate contributes to the total running time.
Correctness
A useful loop invariant is that, immediately before testing position , none of the elements at positions through matches the target.
The invariant holds initially because no elements precede position . If position does not match, advancing to the next position preserves the invariant. If it does match, all earlier positions have already been ruled out, so the algorithm returns the first occurrence. If the loop finishes, every element has been tested without a match.
For a finite collection, termination follows because each unsuccessful iteration advances the search position, and there are only finitely many positions.
Complexity
The time complexity depends on where the first match occurs and whether a match exists. For the basic implementation, counting element-to-target comparisons gives:
| Case | Element comparisons | Running time |
|---|---|---|
| First element matches | ||
| First match is at position , counting from | ||
| Only the final element matches | ||
| No element matches |
These running-time bounds assume constant-time access to each successive element and a constant-time comparison. Comparing long strings or structured objects may require additional work.
For a nonempty collection with exactly one matching element, if that element is equally likely to occupy any position, the expected number of comparisons in a successful search is
If a search succeeds with probability , and the same uniform-position assumption holds conditional on success, then
Thus, an average-case claim requires a specified query distribution; it is not determined by the algorithm alone.
The iterative implementation uses auxiliary space, excluding the collection itself. A version that stores all matches additionally needs space proportional to .
Lower bound for unstructured search
Without ordering, an index, or other usable information, an exact search may need to examine every element. If an algorithm reports absence while leaving an element unexamined, that element could contain the target. Linear search therefore has an optimal worst-case bound in the classical model where elements are inspected individually and no additional structure is available.
Variants
Searching for all matches
To find every occurrence, the algorithm continues after finding a match. It examines all elements rather than stopping early. Counting matches can use constant auxiliary space; collecting them requires storage for the results.
Sentinel search
A sentinel is an extra occurrence of the target placed at a known stopping position. It guarantees that the search loop eventually encounters a match, allowing the loop to omit a separate end-of-collection test on each iteration.
Afterward, the algorithm checks whether the match belonged to the original collection or was only the sentinel. Implementations must provide a safe sentinel location. Versions that temporarily replace an existing element must restore it and handle empty collections separately. Sentinel search changes constant factors, not the linear worst-case bound, and is unsuitable when the required modification is unsafe or forbidden.
Searching ordered data
A linear search through an ascending collection can stop when it encounters an element greater than the target. However, some searches still require examining the whole collection, so the worst-case complexity remains linear.
Frequency-based ordering
For repeated searches with known access frequencies, placing frequently requested elements earlier can reduce the expected number of comparisons. With equal per-element testing costs and a fixed set of distinct keys, ordering keys by decreasing request probability minimizes the successful-search comparison average. Such rearrangement is only applicable when changing the collection's order is permitted.
Data representation and practical performance
Linear search fits a linked list naturally because each node leads directly to the next. Repeatedly retrieving list elements by numerical index may require traversing the list from the beginning each time, making an otherwise linear scan quadratic. An efficient implementation follows the links once.
For contiguous arrays, sequential access often makes effective use of the CPU cache and hardware prefetching. This can make linear search competitive on small collections despite its asymptotic disadvantage. Actual performance depends on element size, comparison cost, memory layout, and implementation.
A database table scan uses a related approach: records are examined and tested against a condition. Such a scan can be appropriate when no useful database index exists or when a query needs a large fraction of the records.
Comparison with other search methods
Binary search requires only logarithmically many comparisons on a sorted array, but depends on ordering and efficient access to middle positions. Sorting solely to answer one query may cost more than a single linear scan; repeated queries can justify that preprocessing.
A hash table can provide expected constant-time lookup under suitable assumptions, but requires additional storage, construction, and maintenance. A binary search tree, particularly a balanced one, supports efficient lookup and ordered operations while introducing its own structural overhead.
Linear search is consequently useful for small or unsorted collections, occasional queries, sequentially accessible data, and predicates not supported by an available index. Its central limitation is that unsuccessful searches—and searches whose first match occurs near the end—must inspect nearly the entire collection.