Searching

Linear versus binary search

An interactive lesson with 7 steps, about 6 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Linear search: up to $n$ checks.
• Binary search on sorted data: about $\log_2 n$ checks.
• Doubling the data adds just one step to binary search.

Steps

1. Two strategies
2. A million names
3. Double the data
4. Guess my number
5. The catch
6. Halving the search
7. Everyone on Earth