The most fundamental search algorithm: checking every element in a sequence until the target is found or the end is reached.
Overview
What linear search actually does
Start at index 0. Compare the element there against the target. If it matches, return the index and stop. If it does not, move to index 1 and repeat. If you reach the end without a match, the target is not present.
That is the entire algorithm, and its simplicity is the point: it makes no assumption whatsoever about the data. The array can be sorted, reverse-sorted, or shuffled; it can hold duplicates; it can be a linked list with no random access at all. Linear search does not care, because it never jumps — it only ever steps forward by one.
Parameters
12
Visualization
Step: 0
Enter a target and click Step to start searching.
Algorithm Insight
Linear search examines each element in an array one by one in sequential order.
1.Start from the first element (index 0).
2.Compare current element with the Target.
3.If they match, search is successful!
4.Otherwise, move to the next element and repeat.
Efficiency
Time ComplexityO(N)
Space ComplexityO(1)
Linear Search: A Practical Guide
Check every element in turn until you find the target or run out of array. It is the only search that works on unsorted data, and that is exactly when you want it.
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.
example_01.pyPython
def linear(a, target):
for i, x in enumerate(a):
if x == target:
return i, i + 1
return -1, len(a)
def binary(a, target):
lo, hi, n = 0, len(a) - 1, 0
while lo <= hi:
mid = (lo + hi) // 2
n += 1
if a[mid] == target:
return mid, n
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1, n
data = list(range(1000))
print("1000 sorted elements")
print("%-16s %12s %12s" % ("target", "linear", "binary"))
for name, t in (("first (0)", 0), ("middle (500)", 500),
("last (999)", 999), ("absent (-1)", -1)):
_, lc = linear(data, t)
_, bc = binary(data, t)
print("%-16s %12d %12d" % (name, lc, bc))
# The cost profiles are inverted. Linear search finds the FIRST element
# in one comparison, which binary search needs nine for; binary search is
# unbothered by the last element, which costs linear search a thousand.
#
# Case 1: the data is not sorted, and sorting it costs more than the scan.
import math
n = 1000
print()
print("%-42s %s" % ("one search in %d unsorted items" % n, "comparisons"))
print("%-42s %12d" % (" linear scan", n // 2))
print("%-42s %12.0f" % (" sort, then binary search",
n * math.log2(n) + math.log2(n)))
# Sorting to search once costs about twenty times the scan it replaces.
# The sort pays for itself only across many searches:
print()
print("%10s %14s %18s" % ("searches", "linear total", "sort + binary total"))
for s in (1, 10, 100, 1000):
lin = s * (n // 2)
binr = n * math.log2(n) + s * math.log2(n)
print("%10d %14d %18.0f %s" % (
s, lin, binr, "linear" if lin < binr else "binary"))
# The crossover is around twenty searches on a thousand items. Below it,
# the simple scan genuinely wins.
#
# Case 2: n is small. Case 3: the data is a linked list, where reaching
# the middle is itself O(n) and binary search has nothing to stand on.
#
# And one property that has nothing to do with speed: linear search works
# on any sequence, sorted or not, with only an equality test. Binary
# search needs a total ordering AND the sorted invariant maintained by
# somebody, forever.
Output
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.
Run it in Python
Three searches through the same ten-item list — one that hits immediately, one that has to walk the whole way, and one for a value that is not there at all. The last line counts the average rather than asserting it.
linear_search.pyPython 3
# Linear search: check each item in turn until you find the target.
# No assumptions about the data at all - which is the whole point.
def linear_search(a, target):
for i, value in enumerate(a):
hit = "yes" if value == target else "no"
print(f" index {i:>2}: is {value:>3} == {target}? {hit}")
if value == target:
return i
return -1
data = [38, 12, 91, 5, 56, 23, 72, 8, 16, 2]
for target in (38, 2, 40):
print(f"searching for {target} in {len(data)} items")
i = linear_search(data, target)
print(" ->", f"found at index {i}" if i != -1 else "not present")
print()
# The average is not a claim; it is counted over every value in the list.
comparisons = [data.index(x) + 1 for x in data]
print("comparisons per value :", comparisons)
print("average :", sum(comparisons) / len(data))
print("(n + 1) / 2 :", (len(data) + 1) / 2)
Output
How the code works
for i, value in enumerate(a):The entire algorithm is this loop. There is no precondition to check and no structure to maintain, which is why linear search works on anything you can iterate.
if value == target: return iReturning inside the loop is what makes the best case O(1). A version that records the index and keeps going would always cost n.
return -1Reached only after every item failed. A miss always costs the full n — the worst case and the not-found case are the same case.
comparisons = [data.index(x) + 1 for x in data]For each value, how many comparisons finding it took. Averaged, this lands on (n + 1) / 2: half the list, which is where the usual “half the array on average” figure comes from.
Change one thing
Move 2 to the front of data. The average does not change — you made one search cheaper and nine dearer.
Search for a value in a list of one million: replace data with list(range(1_000_000)) and comment out the print inside the loop. Then compare that with binary search on the same list.
Change the loop to for value in a: and return True/False. That is what Python's in operator does on a list, and it is why x in big_list is slow while x in big_set is not.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Linear search needs the data to be:
It compares each item in turn, so it has no precondition at all. That is its one real advantage: every faster search buys its speed with an assumption about the data.
The program prints an average of comparisons over every value in the list. What does it land on?
Finding item i takes i + 1 comparisons, and averaged over all positions that is (n + 1) / 2 - about half the list, which is where the usual rule of thumb comes from.
Which case costs the full n comparisons?
The loop only stops early on a hit. A miss has to rule out every element, so failure always costs the worst case.
Cheat sheet
Linear Search
Start at index 0. Compare the element there against the target. If it matches, return the index and stop. If it does not, move to index 1 and repeat. If you reach the end without a match, the target is not present.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.