Interactive Binary Search Game
How It Works
We're looking for x which is a random number from 1 to 72;
We have to choose from 72 ordered options;
After each miss, we are told if our miss was more or less than x.
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.
Let's give it a try.
The Winning Strategy
We know that our options are ordered;
We're told if our misses are more or less than x.
Based on these, we can use a divide and conquer strategy.
Let's use being told if our misses are more or less than x 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.
We see why this only works when our options are ordered.
We can see that half-way through our options is our best first guess.
Half-way allows us to throw away half of our options, we're halving the problem.
What do we do next?
We choose the half-way point or our remaining options.
We repeat this strategy until we're left with only one option.
Our x is guaranteed to be one of the half-way 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
The question is - "how many times can we half the number of options before we are left with only one"?
This is a logarithm question, but we don't have to get into that.
Put simply, how many times can we divide our number of options by 2 before we are left with 1 option.
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 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 we will need 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 26 and less than 128 which is 27.
So more than 26 and less than 27, 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.
22 = 4
23 = 8
24 = 16
25 = 32
26 = 64
27 = 128
28 = 256
29 = 512
210 = 1024
Why Is It Called Binary Search
The word binary tells us there are 2 options.
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.
Often times in programming binary searches are the best solution.
Beyond programming, we benefit by understanding the strategy of a binary search, this clear, methodical thinking can help us solve all types of problems.
- Elements of Programming
- Systematic Programming: An Introduction
- Data-oriented design: software engineering for limited resources and short schedules
- More Effective C++: 35 New Ways to Improve Your Programs and Designs
- From Mathematics to Generic Programming
- Design of Design, The: Essays from a Computer Scientist
- Mythical Man-Month, The: Essays on Software Engineering