This is an interview question Steve Balmer said he asked – I think of an integer from 1 to 100. You guess it. If you don’t get it right, I tell you if you were high or low. You want to minimize the number of guesses in expectation.
If the number Balmer thinks of is uniformly drawn from 1 to 100, binary search will give us the lowest number of guesses in expectation.
But what if Balmer draws the integer not uniformly, but from a probability distribution. The probability distribution is expressed as an array, p where p[j] is the probability of picking the number j. What strategy should we choose to guess the number he picks with the lowest number of guesses in expectation?
My attempt: if p[j] is uniform across the integers, then the strategy should become binary search. So, my idea is that we guess the number, j among the numbers not ruled out such that the sum of probabilities to its left and right are as balanced as possible. We keep making guesses per this criterion until we guess the number. I conjecture that this is the optimal strategy, but don’t know where to start trying to prove this.
Or could it be that the “uniformly optimal” strategy that holds for all arrays p does not exist and it depends on the specific array. That would be disappointing.
This problem maps to an optimal binary search tree since every strategy can be expressed as a binary tree. This can be solved with dynamic programming as covered in section 15.5 of the book introduction to algorithms by Cormen et.al. third edition.