Checking every drawer
Linear Search
The analogy
You lost your keys, so you open every drawer in order until you find them. It works on any mess — nothing needs to be tidy — but if the keys are in the last drawer you opened them all.
Visualizer
Every drawer, one by one
step 1 / 105
3
8
1
9
2
7
4
Looking for 37. The data is in no particular order, so there is no clever shortcut available.
📖 In depth — the full reference
Linear search — everything worth knowing
| fact | value | note |
|---|---|---|
| worst / average case | O(n) / ~n/2 probes | every drawer might need opening |
| best case | O(1) | first drawer |
| requirement on data | NONE | its entire superpower — unsorted, linked, streamed: all fine |
| when it WINS | small n, one-off searches | sorting first costs O(n log n) — pointless for a single lookup |
| when it loses | repeated searches on big data | sort once + binary search, or hash it |
| variant: sentinel search | plant target at the end | removes the bounds check per step — a real micro-optimisation from the textbooks |
Python: the built-ins ARE linear search
xs = [4, 2, 7, 2] print(7 in xs) # True — linear scan, O(n) print(xs.index(2)) # 1 — first match, ValueError if absent print(xs.count(2)) # 2 — full scan, always O(n) # first match with a condition — the generator idiom: first_even = next((x for x in xs if x % 2 == 0), None) # `x in big_list` inside a loop is the hidden O(n^2) from m0l9 — # a set makes the same test O(1).
def linear_search(a, target):
for i, v in enumerate(a):
if v == target:
return i
return -1
# works on ANY order, zero preparation
# O(n) — and O(n) to prove absenceCheck yourself
Linear search requires the data to be…
Practice — write it yourself
linear_search(arr, t) checks every drawer one by one: return the first index holding t, or -1. No sorting required — that is the point.
Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser