Binary Search Number Guessing Game: Learn the Algorithm by Playing

Quick answer: Binary search repeatedly halves an ordered set. If a number is between 1 and 100, an optimal player can identify it in at most seven yes/no comparisons because 27 = 128. The game makes the algorithm’s boundaries and off-by-one errors visible.

Play the game
- Ask another person to choose an integer from 1 to 100.
- Set low = 1 and high = 100.
- Guess the middle integer.
- If the secret is lower, move high below the guess.
- If it is higher, move low above the guess.
- Repeat until the number is found.
Start with 50. If the answer is “higher,” the candidates become 51–100. The next guess is 75, then 63 or 88 depending on the answer. Every valid response removes about half of the remaining numbers.
Why seven guesses are enough
One yes/no comparison can separate two possibilities, two comparisons four, and n comparisons up to 2n. Since 26 = 64 is too small for 100 possibilities but 27 = 128 is large enough, the worst case needs seven comparisons. This is logarithmic growth: doubling the search range adds only about one comparison.
The loop invariant
Before every guess, the secret—if the previous answers were consistent—must lie in the inclusive interval [low, high]. The algorithm preserves this statement:
- If guess is too low, new low = guess + 1.
- If guess is too high, new high = guess − 1.
- If equal, stop.
The +1 and −1 matter because the guess itself has already been disproved.
Pseudocode
low = 1
high = 100
while low <= high:
mid = low + (high - low) // 2
ask whether the secret is mid
if equal:
return mid
if secret is lower:
high = mid - 1
else:
low = mid + 1
report inconsistent answers
Worked round
Secret number: 73.
| Round | Range | Guess | Answer |
|---|---|---|---|
| 1 | 1–100 | 50 | Higher |
| 2 | 51–100 | 75 | Lower |
| 3 | 51–74 | 62 | Higher |
| 4 | 63–74 | 68 | Higher |
| 5 | 69–74 | 71 | Higher |
| 6 | 72–74 | 73 | Correct |
Common implementation bugs
- Using low < high and accidentally skipping the final candidate.
- Setting high = mid instead of mid − 1 for an inclusive interval.
- Calculating a midpoint that overflows in fixed-width integer languages; low + (high − low)/2 is safer.
- Applying binary search to unsorted data.
- Returning an arbitrary duplicate when the requirement is first or last occurrence.
Game variations
Reverse roles
The computer chooses the number and the player searches. Count guesses and compare with the theoretical bound.
Find the first true condition
Replace numbers with a monotonic test, such as the first array index where a threshold is exceeded. This is the engineering form of “binary search on the answer.”
Detect inconsistent answers
If low becomes greater than high before a match, at least one answer was inconsistent. This teaches how invariants can detect invalid input.
From game to real software
Binary search supports lookup in sorted arrays, version bisection, threshold detection and parameter tuning when the pass/fail condition is monotonic. Database and library implementations may use specialized indexes; do not assume a hand-written loop is always the best production choice.
FAQ
Why not always guess the average value?
For uniformly weighted integer candidates, the midpoint minimizes the largest remaining set. Different probabilities may justify a different strategy.
Does binary search work on linked lists?
It requires efficient access to the middle; arrays are a better natural fit.
What is the complexity?
O(log n) comparisons and O(1) extra space for the iterative version.



