Part of Lesson Plan: Creating a Number Guessing Game in BYOB/Scratch: A Scaffolding Tool For Teaching Binary Searching in AP Computer Science

Activity Overview / Details

Demonstrate on the board the workings of the binary guessing game with a much smaller range:  1 to 10l

Write the list of numbers on the board

1 2 3 4 5 6 7 8 9 10

A student volunteer says he has thought of a number between 1 and 10 inclusive.

Have the student write the number on a piece of paper that he/she keeps folded.

Let's pretend the number is 7.

Say, "Is the number 5?" (You arrive at this number by dividing (1 + 10)/2 = 5.5.  The integer portion is 5.

The student should say, "too low."

You cross out the numbers from 1 to 5.  The remaining list is now

6 7 8 9 10

Say, "Is the number 8?" (You arrive at this number by dividing (6 + 10)/2 = 8.

The student should say, "too high."

You cross out the numbers from 8 to 10.  The remaining list is

6 7

Say, "Is the number 6?" (You arrive at this number by dividing (6 + 7)/2 = 6.5. The integer portion is 6.

The student should say, "too low."

You cross out the 6.  The remaining number is 7.

Say, "Is the number 7?"

The student should say, "correct."

There are at most log ₂N questions required.

A simple way to say this is that four maximum questions are required for 10 numbers because 2 raised to the power of 4 is 16.  2 raised to the power of 3 is not enough to cover 10 possibilities because it is only 8.