← Computer Science
Searching and speed
See it
Two ways to find a number
- Linear search: check every item, one by one.
- Binary search: in a sorted list, check the middle and throw away half each time.
- Halving is powerful: a million items takes only about 20 checks!
Linear
one by one
Binary
halve it
Fast
~20 checks for 1,000,000