Computer EngineeringGames

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.

Computer setup used for a binary search number guessing algorithm game
Photo by KeepCoding under the Unsplash License.

Play the game

  1. Ask another person to choose an integer from 1 to 100.
  2. Set low = 1 and high = 100.
  3. Guess the middle integer.
  4. If the secret is lower, move high below the guess.
  5. If it is higher, move low above the guess.
  6. 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.

Related guides

Reference

Related Articles