Linear Search
Easy+40 XPCheck each element one by one until you find the target. The O(n) baseline.
No visualization loaded.
Watch
—
Press Run to begin.
Linear search is the most honest way to find something: start at the first box, check it, move to the next, and keep going until you find your target (or run out of boxes). It's exactly the 'open boxes one at a time' idea from the last lesson, now written as an actual algorithm. No cleverness — and that's the point. It's the baseline every faster method has to beat.
▸What is 'O(n)' — that keeps showing up and it looks scary?
It's just shorthand for 'how the work grows as the data grows.' The n means 'the number of boxes.' O(n) means: double the boxes, and in the worst case you do about double the checks. Linear search is O(n) because if the target is last (or missing), you check all n boxes. That's it — Big-O is a rough 'how does this scale' label, not hard math. You'll meet O(log n) next, which is much slower-growing and therefore much better.
▸Does it matter where the target is in the array?
A lot, for speed. If it's the first box, you're done in 1 check (best case). If it's last or not there at all, you check every box (worst case). When we say O(n) we mean the WORST case — we plan for the unlucky run, because that's what could hurt you.
▸Does the array need to be sorted for this to work?
No — and that's linear search's superpower. It happily works on a messy, unsorted pile, because it looks at literally everything. Binary search will be far faster, but only if you first pay to sort. Linear search asks nothing of you.
▸If it's so slow, why learn it at all?
Three reasons: it always works (no preconditions), it's the simplest thing that could possibly work, and it's the yardstick. Every time we say an algorithm is 'fast,' we mean 'faster than just checking everything.' You can't appreciate the shortcut until you've felt the long way.
How the work grows
O(n) is fair — grows in step with the data. Double the boxes and you do about double the checks. It uses no extra memory — it just walks the array you already have.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.