Searching Algorithms
The Everyday Problem of Finding Things
Where is your name on the class register? Which shelf has the book you want? Does this playlist already contain that song? All of these are searching problems: given a collection of data and a target, find out whether the target is there — and if so, where.
Computers search constantly: your phone finds a contact among hundreds, a search engine finds pages among billions. Because searching happens so often, the algorithm chosen matters enormously.
Linear Search — Check Everything
The most obvious plan is the one you would use for an unsorted pile of test papers:
- Look at the first item
- Is it the target? If yes — done, report the position
- If not, move to the next item
- If you run out of items — done, the target is not here
This is linear search (also called sequential search). It is a simple sequence with a loop and a condition inside — nothing more.
Linear search always works. Sorted, unsorted, numbers, names — it does not care. Its weakness is speed: in the worst case (target at the very end, or missing entirely), it checks every single item. For 10 items, fine. For 10 million, painful.
Binary Search — Halve the Problem
Now imagine looking up "Lopez" in a printed phone book. Nobody starts at page 1 and reads every name. Instead you open the book near the middle:
- The page says "Martin". L comes before M — so Lopez must be in the first half. Ignore the second half completely.
- Open the middle of the remaining half. "Kelly"? Lopez comes after — keep the second quarter.
- Repeat, halving each time, until you land on Lopez.
That strategy is binary search:
- Compare the target with the middle item
- If it matches — done
- If the target is smaller, discard the upper half; if larger, discard the lower half
- Repeat on the remaining half until found (or nothing is left)
There is one non-negotiable requirement: the list must be sorted. The middle comparison only tells you which half to keep because the data is in order. Hand binary search an unsorted list and its answers are meaningless.
Why Halving Is So Powerful
Each comparison in binary search throws away half of what remains. Watch what happens to 1000 items:
1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1
About 10 comparisons to search 1000 items. Linear search might need all 1000. And the gap explodes as data grows:
| Items | Linear search (worst case) | Binary search (worst case) |
|---|---|---|
| 100 | 100 checks | ~7 checks |
| 1,000 | 1,000 checks | ~10 checks |
| 1,000,000 | 1,000,000 checks | ~20 checks |
A million items, twenty comparisons. Doubling the data adds just one extra comparison, because one more halving covers it. This is why sorted data is treasure — and why sorting algorithms matter so much.
Choosing Between Them
So is binary search simply "better"? Not always. Choosing an algorithm means weighing trade-offs — a real problem-solving skill:
- Unsorted data, searched once? Linear search. Sorting first would cost more than it saves.
- Short list? Linear search — simplicity wins when there are 8 items.
- Large sorted data, searched often? Binary search, no contest. This is the phone book, the dictionary, the database index.
There is also a lesson in pattern recognition here: "repeatedly halve the problem" is a pattern that appears all over computing, not just in search.
Try It Yourself
Play a number-guessing game: a friend picks a whole number from 1 to 100, and answers only "higher" or "lower".
- Guessing 1, 2, 3, 4… is linear search — up to 100 guesses.
- Guessing 50, then 25 or 75, then halving again… is binary search — 7 guesses always suffice, because 2⁷ = 128 > 100.
If you have ever played that game well, you already invented binary search.
Worked Example — Tracing Binary Search Step by Step
Trace binary search searching for 23 in the sorted list [2, 5, 8, 12, 16, 23, 38, 45, 56, 91] (indices 0 to 9):
| Step | low | high | middle index | middle value | Comparison | Action |
|---|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 16 | 23 > 16 | discard lower half; search indices 5–9 |
| 2 | 5 | 9 | 7 | 45 | 23 < 45 | discard upper half; search indices 5–6 |
| 3 | 5 | 6 | 5 | 23 | 23 = 23 | found at index 5 |
Just three comparisons to find one item among ten — and notice how low and high narrow the search area each time, exactly mirroring a trace table's job of tracking every variable through every step. Now trace what happens searching for 100 (not in the list) using the same method: middle values 16, then 45, then 91, then the search area shrinks to nothing (low exceeds high) — confirming, after just four comparisons, that 100 genuinely isn't there. This second trace matters as much as the first: a correct search algorithm must handle "not found" cleanly, not just "found".
Key Words
- Searching algorithm — a step-by-step method for finding a target item in a collection
- Linear search — check each item in turn from the start; works on any list
- Binary search — repeatedly compare with the middle and discard half; requires a sorted list
- Target — the item being searched for
- Worst case — the most steps an algorithm could possibly need