I thought up this problem and am trying to come up with an optimal solution.
I am thinking of a number uniformly randomly between 1-100, inclusive.
- If you guess the number, you "win".
- Else if you guess incorrectly, but are within 10 of the number, I will tell you "hot".
- Else, I will tell you "cold".
For example, if the number I'm thinking of is 37, guessing any value in [27,36] or [38,47] will be "hot". Any guess not in those ranges except 37 will be "cold".
You are not allowed to guess a number outside of 1-100.
My current approach:
- Guess in increments of 11. I guess 11, if it's hot, the number is in [1, 10] or [12, 21]; if it's cold, I guess 33, 55, and so on.
- Suppose the true number is "hot" at 11. Then, I can guess 1. If 1 is hot, the number must be within [2,10], else [12,21]. I could have also guessed 21 here for similar effect.
- Suppose the true number is within [12,21]. My goal is to split the search space in half again. So I guess 6: if hot, it must be within [12,16], else [17,21].
- Repeatedly split the search space in half this way.
Is there a better algorithm? What would be the runtime?