Best method for finding a number from 1 to n

Question

So I have been reading a bit into algorithms related to this topic:

Suppose we have to guess a number between $1$ and $100$ via guessing: we can only say a number and the possible responses are "too high", "too low" and "correct". The only method that I have seen as the best one is the one that seems more intuitive: your guess is just the sum of the lower and higher bounds divided by $2$. In our case, we would start by $50$, then $25$ (if "too high" is the response) or $75$ (if "too low" is the response), etc.

My question is, going more general, say from $1$ to $n$, is this method still the best? Is there any better method, or any method that is as good as the previous one?

My reasoning is the following: if the number n is very large, and approach of starting by guessing a third of the upper limit could be benefitial, since if the response is "too high", we would have gotten rid of two thirds of the possibilities, even though the probability of getting the "best" answer is smaller as larger the number you take as the denominator.

So I see here a need of balance between the probability of getting the "best" answer (i. e. the one that discards the most numbers) and the outcome this guess gives.

Thanks in advance!

[Note: I think the most benefitial methods if not taking $\frac{1}{2}$ fixed would alternate the constant by which one divides $n$].

Answer 1

From https://en.wikipedia.org/wiki/Binary_search_algorithm on Performance

In terms of iterations, no search algorithm that works only by comparing elements can exhibit better average and worst-case performance than binary search.

And these are the only two metrics that matter for most algorithms.

In the real world You could find a reason to guess differently. When there are more factors, e.g. if the worst case is unacceptable (You are only rewarded for guessing in less than x attempts) then perhaps choosing the guess in every step at random, within the range known to still be possible, would give better short term results.

If the number is not actually random (it's a game and the opponent might stay away from numbers that a binary search would easily find), but we're still concerned with the worst case - the average is closer to the worst case, but it's still the best worst case You can get.