Algorithm for approximate number finding

Question

Consider the following game:

• John and Peter agree on a number n.
• John chooses a number x between 1 and n.
• Peter makes a series of guesses k between 1 and n. For each guess:
  • If x/2 ≤ k ≤ 2x, then Peter wins.
  • Otherwise, John tells Peter whether x is less than k.

Peter wants to win in the fewest number of guesses.

There are obvious solutions requiring worst-case O(log n) guesses, but a friend told me that there's a solution with better asymptotic behavior than that. Is my friend right?

Answer 1

Your friend is right. The possible values of x can be partitioned into the ranges {1,2,3,4}, {5,6,…,19,20}, {21,22,…,83,84}, etc., where each range has a single "central" element that covers the whole range; for example, if x is anywhere between 21 and 84, then k = 42 is a winning guess. There are O(log n) such ranges, and Peter can use binary search to find the right range in O(log log n) guesses.