In a previous exercise, we’ve written a program that “knows” a number and asks a user to guess it.
This time, we’re going to do exactly the opposite. You, the user, will have in your head a number between 0 and 100. The program will guess a number, and you, the user, will say whether it is too high, too low, or your number.
At the end of this exchange, your program should print out how many guesses it took to get your number.
As the writer of this program, you will have to choose how your program will strategically guess. A naive strategy can be to simply start the guessing at 1, and keep going (2, 3, 4, etc.) until you hit the number. But that’s not an optimal guessing strategy. An alternate strategy might be to guess 50 (right in the middle of the range), and then increase / decrease by 1 as needed. After you’ve written the program, try to find the optimal strategy! (We’ll talk about what is the optimal one next week with the solution.)
One user implemented an interesting strategy. Based on whether the number was lower or higher than the guess, randomly pick a number in that direction. This code is easy to read, even if it does not achieve the most efficient solution (and depends a little bit on randomness).
Here is one user solution, implementing binary search:
The problem given in this exercise is called a search problem - the objective is to find something. It is solved by an algorithm called a search algorithm - an algorithm designed to find something. Not rocket science, I know, just terminology.
The most optimal solution to this problem requires an algorithm called binary search, the most efficient search algorithm on sorted lists (for those who know about computational complexity, binary search is an
O(log n) algorithm).
In a nutshell, binary search picks an element from a sorted list, then decides (based on some feedback of the target), whether to look earlier or later in the list. In the optimal form, the binary search algorithm will always look at the “center” of the list in question. The catch is that binary search relies on having the original list in question be sorted, or ordered either smallest to largest or largest to smallest.
Let’s go through an example. Say you have this list:
my_list = [-10, 1, 2, 6, 7, 12, 21], and we are trying to find the element
12 in the smallest number of steps. This means we want to search through the list until we find
8, and keep track of the index we look at. The binary search algorithm will start by looking at the item in the middle (in this case
6). We then task, is
6 less than or greater than our target (
12)? It is less, so we need to look at the RIGHT HALF of the list. This means our new list we are looking at is
[7, 12, 21]. We again look at the “center” element (
12), and compare. It is
12, our target, so we are done!
In code, we can accomplish this with a
while loop. We want to keep going until either we haven’t found the element, or our guess is equal to the element. The end conditions are
len(my_list) == 0 or
guess == target, so the
while loop continues while those two conditions are NOT met.
The function will look something like this (in Python 3), assuming the list is sorted from smallest to largest:
A few tricky things to note from the code:
guesshas to be given a value to start, but it doesn’t matter what that value is as long as it is not equal to
target. (Why? because if
guesswere to start out equal to
target, the loop will never happen.)
ifstatement: if the
guessis less than the
target, or if
guessis greater than the
target. In the case of the
guessbeing less than the
target, I want to look at the half of the list on the RIGHT side of the
guess. The way I wrote it here, I am including the
guesselement in the sublist - this is not hugely important, since we will most likely remove that element later in the process anyway.
whileloop after the
ifstatement to see the progress of the code.
Lets way we wanted to add “monitoring” to our code. How many times did the
while loop execute? Let’s just add a counter!
Try changing the value of
target and see what happens!
If you are feeling excited about this code and want to play more, try this bonus challenge: what happens if the list is sorted from largest to smallest? What has to change in the code?
So, to answer the original question, there are two things that need to be modified from our code snippet above:
range(0, 100), so you can either construct the list that way, or compute the guesses on the fly without the list (like in the sample solution above).
There are many ways to solve this problem! Try a few of them and see what you like.