Finding Things Fast

Lesson 8 of 10 · 7 min · Free, no account needed

What you will learn

Binary search checks the middle of a sorted list and throws away the half that can't hold the answer.
Each check halves what's left, so 100 items need at most 7 checks and a billion need 30.
mid = (low + high) // 2: // divides and drops the remainder. % gives the remainder itself.

I'm thinking of a number from 1 to 100.
After each guess I say higher or lower. How few guesses can always find it?
Game: 100 doors, one treasure. Beat 7.
Tap a door. The robot's sensor says left or right, and the wrong half goes dark.
Two robots look for door 73.
Run both, then tap the robot you'd send next time.
Halving has a name, and a line of code.
Binary search finds something in a sorted list by checking the middle and throwing away the half that can't hold it.
Each check halves what's left: 100, 50, 25, 13, 7, 4, 2, 1. That's 7 checks.
The middle index is mid = (low + high) // 2. // divides and drops the remainder: 14 // 2 is 7, 15 // 2 is also 7.
% gives that remainder: 15 % 2 is 1. Watch both run.
You are the search. Move the fences.
The yellow card is mid. Drag low or high to the right card, until you find 70.
One step of binary search, in code.
Step through it. Watch which fence moves.
A video glitches at one moment in 64 minutes.
Each check plays the middle and asks: glitch yet? How many checks to narrow it to 1 minute?
How many guesses are always enough for a number from 1 to 1000?
low = 0 and high = 15. Which card does the search check first?
Tap it.
How far does halving go?
Drag the size of the list up to a billion.

Lessons are interactive and need JavaScript. Turn it on to play them.