Optimal algorithm to guess any random integer without limits?

Question

Guessing Game In Range $[1, n]$

The classical guessing game goes something like this...

1. Our friend thinks of an integer between $1$ and $100$ (let's say they pick $42$).

2. We try to guess that number with the fewest guesses possible: $$ 100, 3, 7, 30, ... $$

3. But every time we guess, they say whether the actual number is higher or lower than what we guessed... $$ 100(lower), 3(higher), 7(lower), 30(lower), ... $$

There is actually an optimal solution to this problem. By knowing whether their number is higher or lower than our previous guess, we can always choose our next guess in exactly the middle of the remaining range... $$ \begin{array}{|c|c|c|c|c|} \hline \text{#} & \text{Options Range} & \text{Number of Options} & \text{Guess} & \text{42 Is Higher Or Lower} \\ \hline 1. & 1...100 & 100 & 50 & \text{Lower} \\ \hline 2. & 1...49 & 49 & 25 & \text{Higher} \\ \hline 3. & 26...49 & 24 & 37 & \text{Higher} \\ \hline 4. & 38...49 & 12 & 43 & \text{Lower} \\ \hline 5. & 38...42 & 5 & 40 & \text{Higher} \\ \hline 6. & 41...42 & 2 & 41 & \text{Higher} \\ \hline 7. & 42...42 & 1 & 42 & \text{Win} \\ \hline \end{array} $$

By using this method we are reducing the number of remaining options by roughly a half with each guess. It took us only $7$ guesses to guess a random number from $1$ to $100$.

Infinite Guessing Game $[1, \infty)$

What if we ask our friend to pick an integer $k$ between $1$ and infinity?

Is there an algorithm which can be proven to be the most efficient in terms of the average number of guesses for finding the answer?

Can it be proven that there can not exist such an algorithm?

My guess is that we need to solve this problem in two separate steps:

1. Find an upper-bound $n$ that is higher than $k$.

2. Solve the original problem in the range $[1,n]$.

If we had all the time in the universe, and because the number $k$ is a finite number, we will guess it eventually.

We can even define some possible ways of finding $n$:

• Counting from 1 upwards. $1, 2, 3, 4, ...$ (Takes exactly $k$ guesses to reach the answer.)
• Guessing a random number in the sub-range of possibilities. (How to define selecting a random number between $1$ and infinity?)
• Squaring our guess until we find an upper bound. $10, 100, 10^4, 10^8, 10^{16}, ...$
• Cubing our guess until we find an upper bound? $10, 1000, 10^9, 10^{27}, ...$ (What if we raise to an even higher power?)
• Exponentially increasing our guess until we find an upper bound. $10, 2^{10}, 2^{2^{10}}, ...$

We could keep defining different techniques like these forever.

The questions are:

1. Are all these techniques equally valid?
2. If not, how can they be ordered in terms of efficiency?
3. If the number $k$ can be anywhere between $1$ and $k$, does this automatically mean that the average number of guesses for any technique tends to infinity?
4. The problem is not only finding the upper-bound as quickly as possible, but also finding it in a way that after we have found it we can find the number itself as quickly as possible.

Double-Infinite Guessing Game $(-\infty, \infty)$

You know the question to this...

Answer 1

A practical approach to this is to start with $n=1$ (or $n=$ any positive integer you like), and double your guess until you reach an $n\ge k$. Then you can conduct your binary search on the remaining possibilities $n/2 < k < n$.

This can't be proven to be the most efficient method, because to do that you would need to know the probability of each $k$, which presumably you don't. But it is an approach I have used in more than one computer programming problem.

By the way, your Doubly Infinite Guessing Game can be reduced to the Singly Infinite version, simply by guessing $n=0$ at your first turn.