Linear search walks an unsorted sequence one element at a time, returning the first match. O(n) — the only option when the data is unsorted or a tree/hash isn't available.
It is the simplest search algorithm and the baseline every other search method is measured against. This page covers how it works, a traced example, practical variants, and the point at which a hash set or binary search becomes the better choice.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(1) |
Θ(n) |
O(n) |
O(1) |
Iterate from index 0; compare each element to the target; return on the first match (or -1 / None if the loop finishes). Best case O(1) when the target is at the front; worst and average O(n).
def linear_search(arr, target):
for i, x in enumerate(arr):
if x == target:
return i
return -1
print(linear_search([3, 1, 4, 1, 5, 9, 2, 6], 5)) # 4
# Pythonic equivalents:
arr = [3, 1, 4, 1, 5, 9, 2, 6]
print(arr.index(5)) # 4 — raises ValueError if absent
print(5 in arr) # True
print(next((i for i, x in enumerate(arr) if x > 4), -1)) # 4list.index and the in operator do this in C — faster than a Python-level loop.The algorithm keeps a single index and compares the element at that index to the target. Every rejected element is never looked at again, so the scan visits each position at most once. If the target is absent, all n elements are compared and the function returns -1. On average, for a target that is present and equally likely to be anywhere, about n/2 comparisons are needed; that constant factor disappears in Big-O, so the average case is still Θ(n).
Space usage is constant: one index variable and the target, regardless of input size. Linear search is also trivially correct and easy to reason about, which is why it is the reference implementation used to test faster search structures. When the data is only ever traversed once, as with a file read line by line or rows streamed from a database cursor, there is no opportunity to build an index, and a linear scan is optimal: any algorithm must look at every element at least once to prove that a target is absent.
Linear search is less a single algorithm than a pattern that underlies many everyday operations: in, list.index, str.find, any(), min(), and filtering rows in a table without an index are all linear scans. A few variants are worth knowing:
def find_all(arr, target):
"""Every index where target appears."""
return [i for i, x in enumerate(arr) if x == target]
def find_last(arr, target):
"""Scan from the right; first hit is the last occurrence."""
for i in range(len(arr) - 1, -1, -1):
if arr[i] == target:
return i
return -1
def sentinel_search(arr, target):
"""Append the target so the loop needs no bounds check."""
n = len(arr)
arr.append(target)
i = 0
while arr[i] != target:
i += 1
arr.pop()
return i if i < n else -1
print(find_all([3, 1, 4, 1, 5], 1)) # [1, 3]
print(find_last([3, 1, 4, 1, 5], 1)) # 3
print(sentinel_search([3, 1, 4], 9)) # -1The sentinel version removes one comparison per iteration (the i < n check) by guaranteeing that the loop terminates. It matters in low-level languages; in Python the built-in list.index is faster still because the loop runs in C. Searching for a predicate rather than an equal value (the first element greater than 4, the first record with a given status) is the same algorithm with a different comparison.
Linear search has no preconditions: the data does not need to be sorted, hashable, or stored in a random-access structure, so it also works on linked lists, generators and streams. For small collections (tens of elements) it frequently beats more sophisticated structures in practice because it walks memory sequentially, which suits CPU caches and prefetchers, and has no hashing or branching overhead. Once the same collection is searched repeatedly, the cost adds up: k lookups cost O(kn). Converting a list to a set costs O(n) once and turns each subsequent membership test into O(1) on average, and sorting once (O(n log n)) enables O(log n) binary search.
| Method | Precondition | Per lookup | Setup |
|---|---|---|---|
| Linear search | none | O(n) | none |
| Binary search | sorted, random access | O(log n) | O(n log n) sort |
| Hash set / dict | hashable keys | O(1) average | O(n) build, extra memory |
| Balanced BST | ordered keys | O(log n) | O(n log n) build |
if x in some_list inside a loop over another list is O(n·m). Convert the inner list to a set first.list.index raises ValueError when the value is missing; decide whether you want an exception or a -1/None return and be consistent.abs(x - t) < eps) instead.