The Guessing Game

Binary Search

How many questions maximum do you think you need to ask to be sure you know what number they thought of? Would you believe me if I told you that you never need to ask more than seven questions to know for sure which number between 1 and 99 they chose? 
 
[Note: If you have been clicking through these screens on the Guessing Game without actually writing any code, then the program panel to the left here will be blank, and you will find it harder to follow the text (and much harder to understand what programming is all about). If that's what you want to get out of this session, or if you really have been entering code all along, but you are unsure if you are on the right track, then click this button to see what I think you might have written by now:
If you had your own code and the button replaced it, you can get your code back by clicking this button:
You really should be writing your own.

Also, at any time you can select the text in the panel, copy it, then paste it into a notepad app and save it (which is probably a good idea anyway: "Save early, save often")]


People usually try to psych out the other person to guess what number they might have chosen, based on what numbers they know that person to be partial to, like maybe their birthday or Christmas or something like that. But the other person might also game your gaming them, and choose a number for its obscurity or because they think it's not what you might assume.

The scientific way to do this is what I call "Lion* Hunting." You imagine yourself a big game hunter, and you are coming to this forest, and you want to catch the lion in it. So you divide the forest in half. The lion is either on the north side of the line, or on the south. Then you take that half and divide it in half again, so the lion is either on the east side or the west. If your first question is

"Is your number less than 50?"
then no matter how they answer, yes or no, you already have half as many numbers to search. Do you see how that works?

So, what question do you want to ask each time around? Can you think of a way to ask it, so it's (mostly) the same question each time through? If you tried and still can't figure out how, don't worry about it, I didn't think it up myself either. 20 million programmers didn't invent it, every one of us got it from somebody else, except some mathematician 60 or 70 years ago figured it out. The rest of us all heard (or read) about it and copied the idea.

When you are ready, turn the page.

 
Five Basic Concepts
Sequence
Iteration
Conditional
Variables
Input/Output

 

<<Previous | ToC | Next >>

[2021 June 8]

*Lion The name is a pun on the idea of hunting by drawing lines (sounds like "lions") across the data to divide it in half.