Binary Search: The Optimal Number-Guessing Game
Play a 1-to-100 number-guessing round and feel the range cut in half each guess; a billion items found in 30 tries—how fast log n really is
THE QUESTION THIS PAGE ANSWERS
ANSWER FIRSTWhat is the key idea behind “Binary Search: The Optimal Number-Guessing Game”?
Play a 1-to-100 number-guessing round and feel the range cut in half each guess; a billion items found in 30 tries—how fast log n really is
Make the claim earn its place. Use this page as a decision aid, not a definition to memorize. Connect the idea to one real task, one observable result, and one failure that would change your mind.
Write one question you could answer with evidence after trying this idea.
A conclusion that sounds complete but leaves the key assumption untested.
The system has already picked a number from 1 to 100. The strip below is every candidate: tap any number to guess—I'll tell you too high or too low, and eliminated numbers gray out. First guess randomly by instinct and note the count, then hit “Guess by binary search” for the textbook answer. Watch: each binary guess cuts the lit region exactly in half.
The power of “cut in half” really shows when data gets big. Tap a data size below, see how many binary guesses you need at most, then watch the “fold in half” animation. Watch: data ×10,000, and the try count only climbs from 7 to a bit over 20.
⚠️ Important premise: binary search's ticket in is “sort first”
The guessing game works because numbers have a natural order—“too high” only means something then. Swap in a dictionary with shuffled page numbers, flip to the middle and see “cat,” and you have no idea whether “dog” is left or right—binary search dies on the spot. So to enjoy O(log n) search, you pay the sorting cost first—how sorting works and how expensive it is is exactly next lesson's star.
Flip a dictionary / phone book
Looking up “Wang” you don't start at page one: flip to the middle, compare the spelling, toss half—the motion in your hands is binary search.
git bisect finds the bad commit
One of 1000 commits introduced a bug? git jumps to the middle commit for you to test, keep the bad half / drop the good half, lock the culprit within 10 tries.
Guess the price / tune a parameter
“How much is this bottle?”“Too high.”“Too low.”—TV price-guess segments: the pros are doing binary search in their heads. Manual hyperparameter search is the same move.
The algorithmic cost curve in “Interactive 1 · Number-guessing game”
“The system has already picked a number from 1 to 100.” is not asking you to memorize steps. It trains you to spot repeated work: as the input grows, how many comparisons, moves, or recursive calls does the program perform?
Find repeated work before declaring something fast
Break “The power of “cut in half” really shows when data gets big.” into three questions: how input size changes, what each round does, and whether the next round can shrink its search space. Big-O describes growth, not an exact time on every machine; constants, memory, and data distribution still matter.
- Power of cutting in half : 100 candidates → 7 tries; a billion candidates still only 30—that's O(log n)
- Not luck—a guarantee : binary search gives a worst-case upper bound; engineering wants determinism
- Order is the premise : a shuffled dictionary can't be flipped; to use binary search, pay for sorting first (next lesson)
Theoretical optimum is not always practical optimum
When AI writes an algorithm, trace a small input by hand and benchmark progressively larger inputs. That turns ““How much is this bottle?”“Too high.”“Too low.”—TV price-guess segments: the pros are doing binary search in their heads.” from a slogan into a performance claim you can check.
From “Interactive 1 · Number-guessing game” to “Interactive 2 · A billion items in only 30 tries”
“Interactive 1 · Number-guessing game” grounds the problem in “The system has already picked a number from 1 to 100. The strip below is every candidate: tap any number to guess —I'll tell you too high or too low, and eliminated numbers gray out. First guess randomly by ins…”. “Interactive 2 · A billion items in only 30 tries” then moves it toward “The power of “cut in half” really shows when data gets big. Tap a data size below, see how many binary guesses you need at most, then watch the “fold in half” animation. Watch: data ×10,000, and the try count o…”. Together, they show that the lesson is not just a conclusion to remember, but a claim with conditions.
Carry the judgment into the next situation
For a real task, find the repeated work first, ask how input size changes, and use a small benchmark to verify the theoretical judgment. Complexity should not become a label detached from the situation.
- “Interactive 1 · Number-guessing game”: The system has already picked a number from 1 to 100. The strip below is every candidate: tap any number to guess —I'll tell you too high or too low, and eliminated numbers gray out. First guess randomly by ins…
- “Interactive 2 · A billion items in only 30 tries”: The power of “cut in half” really shows when data gets big. Tap a data size below, see how many binary guesses you need at most, then watch the “fold in half” animation. Watch: data ×10,000, and the try count o…
- “The closing point”: Everyday form : dictionaries, git bisect for bad commits, price guessing—all binary search
The final “The closing point” brings the discussion to “Everyday form : dictionaries, git bisect for bad commits, price guessing—all binary search”. The useful thing to carry forward is knowing which judgments must be revisited when input, scale, or risk changes.
What this lesson wants to share
- Power of cutting in half: 100 candidates → 7 tries; a billion candidates still only 30—that's O(log n)
- Not luck—a guarantee: binary search gives a worst-case upper bound; engineering wants determinism
- Order is the premise: a shuffled dictionary can't be flipped; to use binary search, pay for sorting first (next lesson)
- Everyday form: dictionaries, git bisect for bad commits, price guessing—all binary search
I turned one judgment from this article into a small experiment I could run today. Knowing what to observe next is more useful than simply remembering the conclusion.
After reading this, I first looked for the conditions behind the idea instead of copying the method into a project. That order made the later trade-offs much clearer.
When this judgment reaches real work, which constraint should be added first? I am curious which step matters most between reading and the first practical attempt.
No discussion on this article yet.