If you have your wits about you, you will realize that you can win this game a lot faster than the last one. This is because your wrong guesses give you information about what you should guess next. If your last guess was too high, then your next guess certainly shouldn't be higher. If your last guess was too low, then your next guess certainly shouldn't be lower. Knowing this, can you come up with a good strategy for finding the element quickly?
Now you may be wondering what all this has to do with sorting. If we have a list of numbers and we want to find a specific number in the list, then it seems like there's not much we can do but look at each element of the list until we find the number we're looking for. If we're really unlucky, it will be the last element we look at and we'll have to look at the whole list.
But what if the list is sorted? Well, then we can pick an element in the list and compare it with the element we're searching for. If the two elements are equal, then we've found what we're looking for and we're done. If the element we're looking for is smaller, then we know that it comes before the element we are looking at. If the element we're looking for is larger, then we know that it comes after the element we're looking at. Sound familiar? It should, since this is just the second version of The Guessing Game.
This shouldn't be too surprising, since we do this kind of searching any time we look up a name in a phone book or a word in a dictionary. The only thing we need is a sorted list. Hey, isn't that what Martha was doing in the first place?