Interactive Binary Search Game

We're looking for x.
x is a random number from 1 to 72;
Our options are ordered from smallest to largest (1...72).
If we guess wrong we're told if x is more or less than our miss.
We only have 7 guesses to find x.

How do we find x?
We could guess randomly, but that doesn't seem like a good strategy.

With the right strategy, we can find x in 7 or fewer guesses every time, guaranteed.

The Winning Strategy

There are two important conditions for using this strategy which are as follows:

We know that our options are in order
We're told if x is more or less than our misses

Because both are true for us, we can use a divide and conquer strategy.

We are told if our misses are more or less than x, let's use that to our advantage,
How? If our miss is less than x then all guesses less than our miss are wrong too, and if our miss is more than x then all guesses more than our miss are wrong.
It makes sense why this only works when we have ordered options.

We can see that half-way through our options is our best first guess.
Why half-way?

Halfway allows us to throw away half of our options.

What do we do next?
We choose the halfway point of our remaining options.
We repeat this strategy until we're left with only one option.
Our x is guaranteed to be one of the halfway guesses.

What's Luck Got to Do With It

Luck is not a factor in finding x in less than 8 guesses.
Luck is a factor in how many guesses of our 7 that we use.
For example, we could get lucky and x is the half-way point of our options;
then we would only use 1 guess, but this was luck.

We are guaranteed to find x in less than 8 guesses, but anything less than 7 is luck.
It's better to be lucky than good, but we want to be both.

How Many Guesses Do We Need

Binary search is fast because of how fast it reduces the number of options to choose from.
To know how many guesses a given search will take we need to find how many times we can half our options until only one remains.
This is a logarithm question.

Put simply, how many times can we divide our options by 2 until we have only 1 option left. 1. 72/2 = 36 2. 36/2 = 18 3. 18/2 = 9 4. 9/2 = 5 (rounded) 5. 5/2 = 3 (rounded) 6. 3/2 = 2 (rounded) 7. 2/2 = 1 We see that for 72 options we need 7 halvings. We divide by 2 because it halves our options.

Powers of Two

If we are familiar with the powers of 2, and we should be, we can easily know the max number of guesses needed to find an x in an ordered set of options.
We just have to find the power or 2 that is more than or equal to our number of options.
In this case we have 72 which is greater than 64 which is 2⁶ and less than 128 which is 2⁷.
So more than 2⁶ and less than 2⁷, this is why we can guarantee that we can find x in 7 guesses. If we increased our number of options to 129, then we would need 8 guesses.
If we increased our number of options to 257, then we would need 9 guesses.
This pattern continues.

Here are the first 10 powers of 2.

2¹ = 2
2² = 4
2³ = 8
2⁴ = 16
2⁵ = 32
2⁶ = 64
2⁷ = 128
2⁸ = 256
2⁹ = 512
2¹⁰ = 1024

Why Is It Called Binary Search

The word binary comes up a lot in the tech world, for example a binary tree, binary simply means 2 choices.
What are they?
Each step of our search we are halving our options into 2, keeping one half and discarding the other.
This is why it's called binary search.

Conclusion

Often times in programming, binary searches are the best solution.
Beyond programming, we benefit by understanding the strategy of a binary search.
Clear, methodical thinking helps us solve all types of problems.