Tag: binary search

Computer science and psychology

This morning, when I got back from the gym, my wife and daughter were playing 20 questions, with my wife having just taught my daughter the game.

Given that this was the first time they were playing, they started with guessing “2 digit numbers”. And when I came in, they were asking questions such as “is this number divisible by 6” etc.

To me this was obviously inefficient. “Binary search is O(log n)“, I realised in my head, and decided this is a good time to teach my daughter binary search.

So for the next game, I volunteered to guess, and started with “is the number \ge 55“? And went on to “is the number \ge 77“, and got to the number in my wife’s mind (74) in exactly  7 guesses (and you might guess that \lceil log_2 90 \rceil (90 is the number of 2 digit numbers) is 7).

And so we moved on. Next, I “kept” 41, and my wife went through a rather random series of guesses (including “is it divisible by 4” fairly early on) to get in 8 tries. By this time I had been feeling massively proud, of putting to good use my computer science knowledge in real life.

“See, you keep saying that I’m not a good engineer. See how I’m using skills that I learnt in my engineering to do well in this game”, I exclaimed. My wife didn’t react.

It was finally my daughter’s turn to keep a number in mind, and my turn to guess.

“Is the number \ge 55?”
“Yes”

“Is the number \ge 77?”
“Yes”

“Is the number \ge 88?”
“Yes”

My wife started grinning. I ignored it and continued with my “process”, and I got to the right answer (99) in 6 tries. “You are stupid and know nothing”, said my wife. “As soon as she said it’s greater than 88, I knew it is 99. You might be good at computer science but I’m good at psychology”.

She had a point. And then I started thinking – basically the binary search method works under the assumption that the numbers are all uniformly distributed. Clearly, my wife had some superior information to me, which made 99 far more probable than any number between 89 and 98. And s0 when the answer to “Is the number \ge 88?”turned out to by “yes”, she made an educated guess that it’s 99.

And since I’m used to writing algorithms, and  teaching dumb computers to solve problems, I used a process that didn’t make use of any educated guesses! And thus took far many more steps to get to the answer.

When the numbers don’t follow a uniform distribution, binary search works differently. You don’t start with the middle number – instead, you start with the weighted median of all the numbers! And then go on to the weighted median of whichever half you end up in. And so on and so forth until you find the number in the counterparty’s mind. That is the most optimal algo.

Then again, how do you figure out what the prior distribution of numbers is? For that, I guess knowing some psychology helps.