Quickest way to find a number between 0 and 100 if you can verify if it's bigger (or smaller) than another number

Question

If there is a number somewhere between 0 and 100 and you have to find it with the least attempts possible. Every attempt consists of you checking if the number is smaller (or bigger) than a number in the said interval (0 to 100). My guess would be you start with the half way point.

Is it smaller than 50? yes --> is it smaller than 25---> yes ---> is it smaller than 25 ---> no ---> is it smaller than 37.5 ---> yes...etc

If this is indeed the faster method, what would be the formula that expresses it? If this isn't the fastest method, what is it and how is it expressed mathematically and verbally? Thanks.

Answer 1

Using the exact halfway point is not the fastest method. For example, suppose the number is $98$. Then you get:

$50 \rightarrow 75 \rightarrow 87.5 \rightarrow 93.75 \rightarrow 96.875 \rightarrow 98.4375 \rightarrow 97.65625$

... and only now you know it is $98$

However, if you use whole numbers, (and let's assume we round down)then you are ruling out those very numbers when it is not that number. So again, if the number is $98$:

$50 \rightarrow 75 \rightarrow 87 \rightarrow 93 \rightarrow 96 \rightarrow 98$

and now you got it in $6$ ... and if the number was $99$, you'd know it after these $6$ steps as well.

In fact, with this whole number method, it will be true that you will know the number after at most $\lfloor log_2 99 \rfloor = 6$ steps.

Here is a proof by induction (on $m$) as to why: The general claim is that if you have a choice of $2^m \le n < 2^{m+1} $ numbers, it will take at most $\lfloor log_2 n \rfloor = m$ steps to figure out the number.

Base: $m=0$ ($n=1$)

If there is only $1$ number, you immediately know what that number is, so that takes $0$ steps. And indeed, $\lfloor log_2 1 \rfloor = 0$

Step:

Suppose you have $2^{m+1} \le n < 2^{(m+1)+1} $ numbers left. You pick the halfway number, rounding down if necessary. In the worst case scenario (which is where $n$ is even, and you rounded down for your pick), you are left with exactly $\frac{n}{2}$ numbers. Now, given that $2^{m+1} \le n < 2^{(m+1)+1} $, we have that $2^m \le \frac{n}{2} < 2^{m+1}$ and thus, by inductive hypothesis, it takes at most $m$ more steps to figure out the number from this point on. Given that you just took a guess, that means that it takes at most $m+1$ steps to figure out the number, which is what we need to show.

OK, so we have proven that with a choice of $2^m \le n < 2^{m+1} $ numbers, it will take at most $\lfloor log_2 n \rfloor = m$ steps to figure out the number. So, in your case, it takes indeed at most $6$ steps to figure out the number. Since your method of picking the exact halfway point with rounding to a whole number takes $7$ steps in some cases, your method is not the best.

OK, but how do we know that there is not a better method yet, other than using this method of picking the halfway point, and rounding to a whole number? Well, any other method would at some point have to deviate from this method, and thus at some point it would either not pick a whole number (like your original method), or pick a number that would split the leftover numbers in two piles, with one pile at least $2$ larger than the other. But in either case, that means that in the worst case scenario you end up with a pile of numbers that is at least as big as the pile you end up with using the above method.

But if you have more numbers to choose from, it can, in the worst case scenario, never take less steps to figure out the number than when you have fewer numbers, because it that were so, then you could of course figure out the number with the smaller pile in just as few steps by simply adding some extra numbers and making the pile just as big.

So, given that with some alternative method and in the worst case scenario you always get a pile with at least as many numbers as with the above method, this alternative method cannot take any fewer steps in the worst case scenario. Hence, there is no algorithm that has a worst case scenario that has better performance than the above method... meaning that the minimum number of moves in the worst case scenario is indeed $6$.

Answer 2

Yes, this is the most efficient search method if you can only get a "yes" or a "no" answer on each attempt. Because there are two possible responses on each attempt, it is known as a binary search - see https://en.wikipedia.org/wiki/Binary_search_algorithm.

Answer 3

The other answers have confirmed that this is the best method but did not mention how you can see that you cannot get much better. With $7$ tests and only $2$ possibilities each, there are $2 ^ 7 = 128$ possible result sets so there is some chance of distinguishing $101$ cases if the tests are chosen well. With only $6$ tests, there would be at most $2 ^ 6 = 64$ possible result sets and hence no hope of distinguishing $101$ cases.

I say, "cannot get much better". As I just said, you won't be able to get the worst case below $7$ but, with some tweaking, you might get the average a little lower.

This type of analysis may prove that you cannot do better than a certain number of tests but does not prove that it is possible. For example, suppose there were $3$ possible results to each test $<$, $=$, and $>$ then since $3 ^ 5 > 101$ you might hope that $5$ tests would be sufficient but this alone would not prove it. You would need to find an algorithm with a worst case of $5$ steps or prove it in some other way.