Searching Algorithms
Two ways to find a value in a list. One checks every item in order. The other only works if the list is already sorted, but when it can be used, it's dramatically faster. Watch both, then see exactly how much that difference matters as lists get bigger.
Linear Search
Check each item, one at a time, from the start. Works on any list, sorted or not, but in the worst case, you check every single item.
Code
Controls
Exam tips
- Works on any list, sorted or not, no pre-processing needed.
- Worst case O(n), target could be last, or absent entirely.
- Best case O(1), target happens to be first.
- Simple and reliable, but doesn't scale well for very large lists searched repeatedly.
Binary Search
Only works on a sorted list, but it's much faster. Check the middle item: if it's not the target, you instantly know which half to ignore completely, and repeat on the remaining half.
Code
Controls
Exam tips
- Requires the list to be sorted first, otherwise results are unreliable, as the next section proves.
- Worst and average case: O(log n).
- Each comparison eliminates half of whatever range remains.
- If you'll search the same list many times, the one-off cost of sorting it is almost always worth paying.
What if the list isn't sorted?
Here's proof, not just a rule to take on trust. This list is not sorted, but it definitely contains the number 8, sitting right at position 1. Step through and watch what binary search actually does with it.
Controls
Why log n? Halving it by hand
Pick a list size, then keep halving it, on paper, that's exactly how you'd work out roughly how many comparisons binary search needs in the worst case.
List size
| Step | Current size | ÷ 2 (rounded down) |
|---|
How much does it matter as lists get bigger?
Worst-case comparisons needed to find (or rule out) a value, for lists of increasing size. This is the same O(n) vs O(log n) gap from the Big O work, here it is on the exact algorithms that gap describes.
| List size | Linear search (worst case) | Binary search (worst case) |
|---|---|---|
| 10 | 10 | 5 |
| 100 | 100 | 8 |
| 1,000 | 1,000 | 11 |
| 10,000 | 10,000 | 15 |
| 1,000,000 | 1,000,000 | 21 |
Doubling the list size adds one whole extra step to linear search's worst case for every doubling, but binary search only ever adds one more comparison, no matter how large the list gets. That's the practical meaning of O(n) vs O(log n).