I am thinking of an integer in the interval [1-15]. You are to try to guess it by telling me intervals and I will tell you if my number lies in that interval.
For example if my number is 6 and you guess [6-9] I will tell yes but if you guess [7-11] I will tell you no but not if my number is higher or lower.
You win by guessing an interval of just one number and that number is my number. Find a strategy that minimizes the expected number of guesses.
I am wondering if there is perhaps some subtlety being missed here by assuming that the binary search is always optimal... In fact, in the literature, it is often stated it becomes non-optimal for small arrays.
As an extreme example, say instead of 15, the array has N=3 elements. I.e, the choices are 1, 2, or 3. It is simple to show the interval guessing of {1}, then {2}, then {3} is a better strategy than first guessing {2,3}.
The first way has an expectation of 2 guesses while the second way has 2.333...
So, some thought must go into the exact answer, such as the details of the endgame.
In fact, there is at least
one paper that claims that the "quadratic search" (a quartile search) for small N is better (less steps) than the binary search, but sadly the paper is almost unreadable due to language difficulties.
Edited on October 23, 2019, 8:29 am
some thoughts
