HERE IS A fun math party trick.
Tell someone to pick a number between 1 and 1,000. Your goal is to guess the number.
For each guess you make, your friend tells you one of three things: you guessed the number, your guess was high, or your guess was low.
Amazingly, if you guess properly, it is possible to get to any number your friend chooses in 10 or fewer guesses.
The trick to this is to constantly be cutting the amount of numbers you have to consider in half. This process demonstrates binary search, a foundational concept in technology. But more on that later.
How to guess the number in 10 steps or under
Suppose your friend chooses the number 334.
Your First Guess: In this game, your first guess should always be 500, halfway between 1 and 1000. So, you guess 500, and your friend tells you that their number is lower. Now you know that the number is somewhere between 1 and 500, and you have knocked out everything between 500 and 1000. You have, in one guess, already gotten rid of half the possibilities.
Your Second Guess:You know that the number is between 1 and 500, so you again take the halfway point between these two, and you guess 250. Now your friend tells you your guess is too low, so you know the number is somewhere between 250 and 500. In just two steps, you have knocked out 750 numbers, and are just looking at about 250 numbers, a quarter of our original set.
Keep Doing This: Your next guess is halfway between 250 and 500, or 375. Your friend tells you this is too high, so now you know that the number is between 250 and 375. You have reduced your range to about 125 possibilities.
The fourth guess is the midpoint of 250 and 375: Unfortunately, this is a decimal number – 312.5, but we can simply round up to 313. This guess is too low, but we have again eliminated half the remaining numbers, leaving us with the 61 numbers between 313 and 375.
Your fifth guess is halfway between 313 and 375: 344. Again, this is too high, but you’re down to the 30 numbers between 313 and 344.
Your sixth guess is halfway between 313 and 344: 328.5, rounded up to 329. Too low. You know the number is between 329 and 344, leaving just 14 possibilities.
Your seventh guess is halfway between 329 and 344: 336.5, rounded up to 337. Too high, but you’re getting close — only the seven numbers between 329 and 227 are left.
Your eighth guess is halfway between 329 and 337: 333. Juuust too low. But now there are just three remaining possibilities — you know the number is between 333 and 337, so it must be one of 334, 335, or 336.
Your ninth guess is the middle option of 335, and you are told that your guess is too high.
And now you know that the number is between 333 and 335. There is only one such number, and so your tenth, and final guess, is 334, your friend’s number.
This process will work for any number between 1 and 1000, and you will always find the number within 10 guesses.
Binary search
This game is a simple example of a binary search process.
This works well for any ordered list, like a directory of employees at a corporation, ordered by name. Suppose we are trying to find a particular name on the list.
We start by comparing the desired name to the middle name in the list. If they match, then yay! We are done.
If the middle name comes after the desired name, we throw out the second half of the list, and just look at the first half.
If the middle name comes before the desired name, we do the opposite — dump the names before the middle name, and just search the second half of the original list. Then we just keep repeating this process, throwing out half the remaining names each time, until we find our name.
This is such a simple, recursive process that it is ideally suited to being run on computers, and this is indeed how most database systems search through sorted lists of data.
One of the coolest things about binary search is that the number of steps you need to find your target increases logarithmically with the size of the set you are looking in. What this means is that if you double the size of your set, you only wind up adding one extra step. If I wanted to find a number between 1 and 2000, my first guess is going to be 1000 (halfway between 1 and 2000), and then I’ll be looking at either the numbers between 1 and 1000 or between 1001 and 2000, and we are back where we started — trying to find one number among a thousand numbers.
Extending this out, if we wanted to find a number between 1 and 1,000,000, we actually only need 20 steps to get to the number. For those of you familiar with logarithms, this is because the base 2 logarithm of 1,000,000 is just under 20.
Processes like this that add steps at a logarithmic rate with respect to the size of the input are pretty rare — usually, if I double the size of my input, I at least double the number of steps I need to take to solve my problem, and often need to add many, many more steps than that.
Binary search is a great example of using a very simple concept — repeatedly cutting my search region in half by always guessing the middle number — and getting a very powerful tool from that concept. This is one of the central, big ideas in math: Start with a simple notion, and discover all the interesting, often surprising, implications of that notion.
- Andy Kiersz
To embed this post, copy the code below on your site
have your say