Binary Search: 20 Questions Find 1 in a Million

Think of a number between 1 and 1,000,000: twenty yes-or-no questions are always enough to find it, and nineteen are not. Here is why.

Think of a number between 1 and 1,000,000: twenty yes-or-no questions are always enough to find it, and nineteen are not. This video shows why, turns the idea into binary search on a sorted list with a step-by-step walk-through in pseudocode, counts its comparisons, and shows the two classic ways to get it wrong.

In this video

Halving the possibilities
Why nineteen questions are not enough
Binary search on a sorted list
Counting the comparisons
Two ways to get it wrong

Details

Length: 8:15
Language: English, with English captions
Production: Written, animated and narrated by an AI system; synthetic voice