Binary search game

The idea

What is binary search?

Binary search finds a value in a sorted list by checking the middle, then throwing away the half that cannot contain it. Repeat until one value is left. Guess the number is the same idea: the numbers 1 to 1,000 are already in order, and each bigger or smaller hint tells you which half to keep.

Speed

Why it is so fast

Every step halves what is left, so the number of steps grows very slowly. The steps needed are the smallest n where 2 to the power of n is larger than the range:

A million numbers take only 20 guesses, because 2 to the power of 20 is 1,048,576.

Code

Binary search in code

This is the same strategy the game rewards, written in Python:

def guess_number(low, high, answer):
    guesses = 0
    while low <= high:
        guess = (low + high) // 2
        guesses += 1
        reply = answer(guess)  # "bigger", "smaller" or "correct"
        if reply == "correct":
            return guess, guesses
        if reply == "bigger":
            low = guess + 1
        else:
            high = guess - 1

Teachers

Use it in class

Play one round on the board with students calling out guesses and watch the bar narrow. Ask how many guesses 1 to 1,000,000 would need. Then let pairs play Duo mode.

More ways to play

Pick your game