Search Race
Linear search checks every item. Binary search keeps cutting the list in half. Pick a target, make your prediction and watch them race!
List size
Level
Your prediction
Linear search
O(n)Checks one by one
Ready
0ChecksComparisons
Binary search
O(log n)Cuts the list in half
Ready
0ChecksComparisons
Race log
Every race you run is recorded here.
The big experiment
Test every possible target on lists from 10 to 1,000 items. How do the two searches grow? Linear grows like n / 2 on average. Binary grows like log2 n.
Linear searchBinary search
Show the numbers as a table
Linear search
- Start at the first item and check each one in order.
- Works on any list, sorted or not.
- A list of 1,000 items can take up to 1,000 checks.
- Time complexity O(n). On average it makes about n / 2 comparisons when the target is in the list.
- Also works on linked lists and data that arrives one item at a time.
Binary search
- Check the middle item. Too small? Throw away the left half. Too big? Throw away the right half.
- Only works on a sorted list.
- A list of 1,000 items needs at most 10 checks!
- Time complexity O(log n). The worst case is ⌊log2 n⌋ + 1 comparisons: 20 for a million items.
- Needs random access (an array), because it jumps straight to the middle.
Try this
Can linear win?Click the very first number in the list and race. Why does linear search win this time?
Not therePress “Not in the list” and race. How many checks does each search need to be sure the number is missing?
Why sorted?Binary search throws away half the list after each comparison. Explain why that is only safe when the list is sorted.