Sign in. It’s quick, free and it’s up to you.
An account is an optional way to support the work we do. Find out more.
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
It’s only a matter of time. driving accounts for 30% of male employment worldwide. When vans trucks light rail taxis are driverless there will be an unemployment disaster.
exactly Patrick, rise of the machines technology is not always a good thing.
I don’t think I’d be ready to trust this technology anyway.
Automation has been killing jobs for centuries and will continue to do so for millennia.
As always people will have to adapt and adjust careers accordingly.
Can’t hold back progress.
Do you have a source for that, Patrick?
Those guys can work at something else. This is a great thing. Can’t wait for driverless cars.
Taxi drivers, van drivers, lorry drivers, bus drivers all looking at this and feeling a bit uneasy I’d imagine… on the plus side if it can take me home from the pub on a Friday night it won’t be the worst thing in the world
I look at advancements in technology in my sector and feel the same uneasiness. Can either sit back and do nothing, or look to try and learn new skills.
Who’s going to clean the puke off the seat before you get in.. Or who will wake up the drunk passenger in the back seat.. Self drive taxis may work well in some places but will not work well at 4am on a Saturday night in Dublin..
I would imagine there will be multiple internal cameras. Plus payment will be by card only. If camera catches a passenger damaging the car i.e. Puking…charge to card straight away.
Problem is technology/AI is advancing so quickly it is now replacing humans rather yhan just impeovibg the work place. Imagine the fin hackers will have with automated vehicles!??
Cheer up, planes still have pilots.
By the time the driver realizes that an accident is imminent it is generally too late to grab control. Safe driving requires forward planning and anticipation. You cannot be plunged into an emergency manual override position moments from disaster and expect to avoid it.
There’s many reported cases by Teslas stopping accidents before the driver even realised one was happening. Loads on dash cam vids and accounts on motoring forums. The tech is already saving lives. Given the number of road deaths here and around the world we’d be mad not to pursue this.
have your say