Did it ever happen to you that a child’s innocent suggestion opened up your eyes to a whole new way of doing something? A few days ago I experienced just the thing. The topic that light was shed upon is binary search, but let me not get too ahead of myself and tell everything from the beginning.
There are six kids in the room, and each one in turn gets posed with the same task: I hid between one and four stones in a bag and you have to determine the number after asking no more than two yes/no questions. To make it more real, I have an actual bag where I hide real stones. Naturally, the kids start by asking about the number of stones directly. “Are there two stones? Are there three?” The first few kids get lucky and guess the number on their first or second try. Finally we get to someone who is not so fortunate and we can start discussing what other types of questions one might ask to guarantee success.
How can they ask about multiple numbers at once? The answer does not come easily. We even further hint that they should come up with a question that asks about one and two at the same time. Suddenly, one girl says, “I want to ask about two and four together.” She needs some help articulating the property that the two numbers have in common and that one and three do not share, but in the end we finally have our two questions. And they are not the two questions that we initially envisioned!
After the class was over, I found myself thinking about this some more. The only way that I have seen binary search done when trying to guess a number in some range is by successively splitting the range in half. So for example, if you’re trying to guess a number between 1 and 100 you would first ask if it’s bigger than 50, then (if say the answer is no) if it’s bigger than 25, etc. An equally effective way, however, would be to consider the number’s binary representation. That is, you can first ask whether the number is odd or even, then ask about it modulo 4 (i.e., what remainder does it leave when divided by 4), followed by modulo 8, etc. It seems very natural and I am a bit surprised that I have never encountered it before. Have you? Are there other, equally natural, ways of doing it?