Counting the comparisons
Take the array [42, 17, 8, 91, 5, 63, 29] and search for 91. The algorithm compares 42, then 17, then 8, then 91 — four comparisons, and it returns index 3.
Now search for 29. That sits last, so it takes seven comparisons. Search for 100, which is absent, and it also takes seven — the algorithm cannot know the target is missing until it has ruled out every element.
So the cost splits three ways. Best case is 1 comparison, when the target is first. Worst case is n, when the target is last or absent. The average over all successful searches is:
(1 + 2 + 3 + … + n) / n = (n + 1) / 2
Roughly half the array. All three cases are O(n) except the best, and it is the worst case that gets quoted, so linear search is an O(n) algorithm with O(1) extra space.
Check every element until you find it
Linear search examines each element in turn until it finds the target or reaches the end.
def linear_search(arr, target):
for i, x in enumerate(arr):
if x == target:
return i
return -1
O(n) in the worst case, O(1) in the best, and n/2 comparisons on average for a successful search.
It sounds like the algorithm you would only teach and never use, and that is wrong. Linear search is the right choice more often than binary search, for a specific set of reasons.
When it beats binary search
| Situation | Why linear wins |
|---|
| Unsorted data | Binary search requires sorting first — O(n log n) |
| Small arrays | Below roughly 50–100 elements, the constant factor decides |
| Searching once | Sorting to search once costs more than scanning |
| Linked lists | No random access, so binary search cannot reach the middle cheaply |
| Streaming data | You cannot index into a stream |
| Finding all matches | Binary search finds one; a scan finds every one |
| Complex predicates | "First element satisfying this arbitrary condition" |
The small-array row matters more than the table suggests. Linear search reads memory sequentially, which CPU prefetchers handle extremely well, while binary search jumps around and defeats them. For arrays that fit in cache, a scan of 100 elements can be faster than 7 binary-search comparisons.
That is why real sorting and searching implementations switch to linear methods below a threshold, and why list.index() in Python — a C-level linear scan — is fast enough that reaching for bisect on a short list is usually not worth the complexity.
The one-sorting-question
The decision is not "linear or binary" but "how many searches will there be?"
sort once + k binary searches: O(n log n + k log n)
k linear searches: O(k × n)
Sorting pays off when k log n plus the sort beats k n — which, roughly, means when k is more than about log n.
| Searches | n = 1,000 | Better |
|---|
| 1 | Scan: 1,000 ops. Sort+search: ~10,000 | Linear |
| 10 | 10,000 vs ~10,100 | About equal |
| 1,000 | 1,000,000 vs ~20,000 | Binary |
And if you are performing many lookups, the real answer is usually neither: build a set or dictionary, which gives O(1) per lookup after O(n) construction. That beats both for repeated membership testing, and it is what most production code should do.
The cases where the O(n) algorithm is the right one
Linear search is the algorithm everybody knows and nobody defends. It is worth measuring anyway, because there are three specific situations where it beats binary search, and one of them -- the total cost including the sort -- is the one people get wrong most often.
Things to try
- Watch the worst case. Set Array Size to 25, then set Search Target to a value that is not in the array and press Auto-Run. Every single cell lights up before the algorithm gives up. That full sweep is what O(n) means.
- Watch the best case. Press Randomize Array, read off whatever value landed in the first cell, and set Search Target to it. Now the search ends after one comparison, no matter how large the array is.
- Prove size drives cost. Set Array Size to 5 and step through a failed search with Next Step, counting the comparisons. Now set Array Size to 25 and do it again. The count scales with the array, one for one — there is no shortcut being taken anywhere.
- Look for the pattern that is not there. Press Randomize Array several times and watch where the target turns up. Unlike every other search on this track, the position of the value in a sorted sense tells you nothing. Linear search has no notion of “too high” or “too low”.
When linear search is the right answer
It gets dismissed as the naive option, which is unfair. Reach for it when:
- The data is unsorted and you will search once. Sorting costs O(n log n). If you only need one lookup, paying that to enable an O(log n) search is strictly worse than one O(n) scan.
- n is small. Below roughly 30 elements the constant factors dominate and a tight linear scan often beats binary search in real time, because it is branch-predictable and walks memory in order.
- The structure has no random access. On a singly linked list you cannot jump to the middle, so binary search is not available at any price.
- The match is not on equality. Finding the first element satisfying an arbitrary predicate needs a scan; there is nothing to bisect on.
What trips people up
- Returning a boolean instead of an index. Callers almost always want to know where, and recovering the position afterwards costs a second scan. Return the index and use −1 (or null) for absent.
- Sorting in order to search once. A single O(n log n) sort to enable one O(log n) lookup is a net loss. Sorting pays off only when it is amortised over many searches.
- Nesting it without noticing. A linear search inside a loop over the same array is O(n²). This is the most common accidental quadratic in real code — a hash set turns the inner search into O(1) and the whole thing into O(n).
- Forgetting duplicates. The basic version returns the first match. If you need all of them, keep scanning after the first hit rather than stopping.
In one line
Linear search trades speed for having no requirements at all. It is O(n) because it may have to look at everything, and it cannot do better because it has no information to exploit — but for unsorted data, a single lookup, or a small array, that is not a weakness. Every faster search on this track buys its speed with a precondition, and linear search is what you use when you cannot pay it.
Variants worth knowing
Early exit on sorted data. If the array happens to be sorted, a scan can stop as soon as it passes the target — still O(n), and it halves the average work on unsuccessful searches.
Sentinel search. Append the target to the end of the array so the loop needs no bounds check — the search always terminates on a match. It removes one comparison per iteration, which mattered in low-level code and is irrelevant in Python.
Finding all matches is where linear search has no competition:
indices = [i for i, x in enumerate(arr) if x == target]
Predicate search — the first element satisfying an arbitrary condition:
first = next((x for x in items if x.status == "pending"), None)
That next with a default is the idiomatic Python for "find the first matching item, or None". It short-circuits, so it stops at the first match rather than building a list.
In Python specifically
The built-in operations are C-level linear scans and are faster than a hand-written loop:
x in items # membership
items.index(x) # first index, raises ValueError if absent
items.count(x) # occurrences
min(items), max(items) # extremes - O(n)
any(p(x) for x in items) # short-circuits on the first True
all(p(x) for x in items) # short-circuits on the first False
any and all with generator expressions are the most useful of these, because they short-circuit: any(x > 100 for x in huge_list) stops at the first qualifying element rather than examining everything.
Two notes on index: it raises rather than returning −1, so wrap it in try or check membership first, and it only finds the first occurrence.
For NumPy arrays the vectorised equivalents operate in C over the whole array:
import numpy as np
np.where(arr == target)[0] # all matching indices
(arr == target).any() # membership
These are still O(n) and considerably faster per element, and they do not short-circuit — the whole array is compared.
Where linear search is the only option
- Unsorted collections that change constantly, where maintaining order would cost more than scanning.
- Streams and generators, where there is no index and data arrives once.
- Linked lists, where reaching the middle is itself O(n).
- Finding every match, or counting occurrences.
- Arbitrary predicates that have no ordering to exploit — "the first log line containing an error".
- Very small collections, where any cleverness costs more than it saves.
That last point deserves emphasis as the practical conclusion: for a handful of items, scan. Introducing a sorted structure or a hash map for a ten-element list adds complexity and usually loses on speed too.
Questions people ask
Is linear search ever better than binary search? Yes — on unsorted data, on small arrays, for a single search, on linked lists and streams, and when finding all matches.
What is the average number of comparisons? About n/2 for a successful search, n for an unsuccessful one.
Should I sort first to use binary search? Only if you will search many times. For one search, sorting costs more than scanning.
What about a set? For repeated membership tests, a set is better than both — O(1) per lookup after O(n) construction.
Why is in fast in Python? It is a C-level loop, so the per-element cost is far below an interpreted loop.
How do I find the first match without scanning everything? next((x for x in items if pred(x)), None) — it short-circuits.
Recap in one screen
- Examine elements in order until found: O(n) worst case, n/2 comparisons on average.
- It beats binary search on unsorted data, small arrays, single searches, linked lists and streams.
- Sequential memory access makes it cache-friendly, which is why small-array scans are genuinely fast.
- Sorting to enable binary search pays off only after roughly log n searches; for many lookups, use a set.
- In Python, use
in, index, any and next — C-level scans that short-circuit where possible.