Determine the exact number between $1$ and $1{,}000{,}000$ using $\log$.

Question

You choose a random number between $1$ and $1{,}000{,}000$. How many questions will it take to determine the exact number? The strategy would be to use binary search and I know the answer is $\log_2(1{,}000{,}000)=20$ Questions, but why?

Answer 1

Write a decimal number $\overline{d_m \cdots d_0}_{10}$ as a binary number $\overline{b_n \cdots b_0}_{2}$. Each $d_i$ and $b_j$ denotes a digit.

In a binary search, a question is actually "$b_i = 1?$", so the number of questions needed is the length of the binary number.

When $m = 5$, $n \le \lceil \log_2 10^6 \rceil = \log_2 1048576 = 20$, so we need $20$ binary digits (a.k.a. questions) to classify the decimal number.

Answer 2

With one question you can find one number among two numbers.

With two questions you can find one number among four numbers. Suppose the numbers are $1,2,3,$ and $4.$ Your first question is, "Is the number greater than $2$"? The answer tells you which two-number subset to find one number among next.

A third question will enable you to find one number among $8$ numbers, because the first question can split the $8$ numbers into two four-number subsets to search.

In general, you can find one number among $2^n$ numbers by asking $n$ questions, because each additional question you ask allows you to handle twice as many numbers.

So if you need to find one number among $k,$ you need $n$ questions, with $n$ chosen so that $2^n \geq k.$ Take the base-$2$ logarithm of each side, and you have $$ n \geq \log_2 k.$$

Therefore, if what you know is $k$ and you want to find $n,$ compute $\log_2 k$ and then round it up to the next integer. The result will be $n$ such that $2^n \geq k.$