"Unbounded" binary search in $\log_2(n) + O(?)$ comparisons

Question

Binary search is the well-known algorithm that compares the input value to an entry in a sorted array, and based on the result then decides to check the same input value against another entry either on the left or the right of that array entry. The number of comparisons needed is O(log(n)), but we can specify the number more exactly as $\log_2(n) + O(1)$

In "Unbounded binary search", There is a secret, positive, whole number, without any information on its upper bound (or the number of bits). Our task is to find the value of the secret number in as few comparisons as possible, where "few" is measured as a function in the value of that secret number.

In each comparison, we get to decide on a number and that number will be compared to the secret number by a black box. The black box then outputs True if the picked number is strictly larger than the secret number, and False otherwise. The cost of calling the black box is 1, regardless of the values involved. We can make all other calculations for free, as long as they don't involve the black box.

A straightforward algorithm starts with 1 and doubles it until the black box outputs True, and then with the found upper bound performs a binary search. This takes $2\log_2(n) + O(1)$ comparisons, or $\log_2(n) + f(n)$, where $f(n) = O(\log(n))$. We say that the number of extra comparisons is "$O(\log(n))$". Quicker algorithms are supposedly possible.

What's the quickest algorithm, that gives the lowest number of extra comparisons needed (for large enough n) versus if we knew the number of bits of the secret number?

Answer 1

Your question was completely solved by Bentley and Yao, An almost optimal algorithm for unbounded sorting, and Beigel, Unbounded searching algorithms. They showed that if $f\colon \mathbb{N} \to \mathbb{N}$ is a monotone recursive function then there exists an unbounded search algorithm performing $f(n)$ comparisons on input $n$ if and only if $f$ satisfies Kraft's inequality $$ \sum_n 2^{-f(n)} \leq 1. $$

Kraft's inequality is a bound on the lengths of codewords in a prefix code. To see the connection, observe that you can encode the transcript of an unbounded search algorithm as a binary string, where 0 means "<" and 1 means "≥". Any two such strings must be different (since the algorithm is correct) and no string can be a prefix of another (since the algorithm would stop upon reaching the prefix), and so the strings form a prefix code, hence $f$ satisfies Kraft's inequality. This was shown by Bentley and Yao.

Beigel showed the other direction: any $f$ satisfying Kraft's inequality corresponds to an algorithm. To see this, partition the unit interval $[0,1]$ into intervals of lengths $2^{-f(1)},2^{-f(2)},2^{-f(3)},\dots$ (in this order), and perform binary search on the interval: imagining that the unknown $n$ is located at the middle of its interval, we can identify any subinterval $I$ of $[0,1]$ with the subinterval of $\mathbb{N}$ consisting of the points of $\mathbb{N}$ contained in $I$, and accordingly, convert a query about $[0,1]$ to a query about $\mathbb{N}$. After $f(n)$ steps, the algorithm has zeroed in precisely on the $n$'th interval, and in particular, has figured out that the answer is $n$.

Concretely, here is an algorithm (suggested by Bentley and Yao) that uses $\log_2 n + O(\log \log n)$ queries: determine $\lceil \log_2 n \rceil$ using your algorithm ($O(\log\log n)$ queries), and then run standard binary search (at most $\log_2 (2n) + O(1)$ queries, since $2^{\lceil \log_2 n \rceil} \leq 2n$). Conversely, any algorithm must use $\log_2 n + \Omega(\log \log n)$ queries, due to Kraft's inequality. So the optimal algorithm uses $\log_2 n + \Theta(\log \log n)$ queries.