Linear search
Look at each item in turn until you find the one you want. It needs no sorting and no setup, so it works on anything. The price is that the work grows in a straight line with the number of items.
831259174
Look for 12, starting from the left. Press play or step forward to start.
1function linearSearch(a, target) {2 for (let i = 0; i < a.length; i++) {3 if (a[i] === target) return i;4 }5 return -1;6}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | the target is the first item |
| average | n | about half the items when the target is present |
| worst | n | the target is last or missing |
| space | 1 | just the index |
Where it breaks
- Searching the same data again and again. Each search costs up to n. If you search often, sort once and use binary search at log n, or build a hash table for about one step per lookup.
- Proving something is missing. Pick Missing 6: it has to check all 8 items, because the last unchecked one could always be the target.
- But it often wins on small data. For a few dozen items, a straight scan through memory is fast and simple. Fancier structures only pay off as n grows.