Hot and Cold Binary Search Game

Question

Hot or cold.

I think you have to do some sort of binary search but I'm not sure how.

Your goal is the guess a secret integer between 1 and N. You repeatedly guess integers between 1 and N. After each guess you learn if it equals the secret integer (and the game stops); otherwise (starting with the second guess), you learn if the guess is hotter (closer to) or colder (farther from) the secret number than your previous guess. Design an algorithm that finds the secret number in lg N + O(1) guesses.

Hint: Design an algorithm that solves the problem in lg N + O(1) guesses assuming you are permitted to guess integers in the range -N to 2N.

I've been racking my brain and I can't seem to come up with a a lg N + O(1).

I found this: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1316188034 but could not understand the diagram and it did not describe other possible cases.

Answer 1

Suppose you know that your secret integer is in [a,b], and that your last guess is c.

You want to divide your interval by two, and to know whether your secret integer lies in between [a,m] or [m,b], with m=(a+b)/2.

The trick is to guess d, such that (c+d)/2 = (a+b)/2.

Without loss of generality, we can suppose that d is bigger than c. Then, if d is hotter than c, your secret integer will be bigger than (c+d)/2 = (a+b)/2 = m, and so your secret integer will lie in [m,b]. If d is cooler than c, your secret integer will belong to [a,m].

You need to be able to guess between -N and 2N because you can't guarantee that c and d as defined above will always be [a,b]. Your two first guess can be 1 and N.

So, your are dividing your interval be two at each guess, so the complexity is log(N) + O(1).

A short example to illustrate this (results chosen randomly):

Guess    Result    Interval of the secret number
 1       ***       [1   , N    ]    // d    =  a   +  b  - c
 N       cooler    [1   , N/2  ]    // N    =  1   +  N  - 1
-N/2     cooler    [N/4 , N/2  ]    //-N/2  =  1   + N/2 - N
 5N/4    hotter    [3N/8, N/2  ]    // 5N/4 = N/4  + N/2 + N/2
-3N/8    hotter    [3N/8, 7N/16]    //-3N/8 = 3N/8 + N/2 - 5N/4
  .        .            .               .
  .        .            .               .
  .        .            .               .

---

Edit, suggested by @tmyklebu:

We still need to prove that our guess will always fall in bewteen [-N,2N]

By recurrence, suppose that c (our previous guess) is in [a-(a+b), b+(a+b)] = [-b,a+2b]

Then d = a+b-c <= a+b-(-b) <= a+2b and d = a+b-c >= a+b-(a+2b) >= -b

Initial case: a=1, b=N, c=1, c is indeed in [-b,a+2*b]

QED

Answer 2

This was a task at IOI 2010, for which I sat on the Host Scientific Committee. (We asked for an optimal solution instead of simply lg N + O(1), and what follows is not quite optimal.)

Not swinging outside -N .. 2N and using lg N + 2 guesses is straightforward; all you need to do is show that the obvious translation of binary search works.

Once you have something that doesn't swing outside -N .. 2N and takes lg N + 2 guesses, do this:

Guess N/2, then N/2+1. This tells you which half of the array the answer is in. Then guess the end of that half-array. You're either in one of the two "middle" quarters or you're in one of the two "end" quarters. If you're in a middle quarter, do the thing before and you win in lg N + 4 guesses. The ends are slightly trickier.

Suppose I need to guess a number in 1 .. K without straying outside 1 .. N and my last guess was 1. If I guess K/2 and I'm colder, then I next guess 1; I spent two guesses to get a similar subproblem that's 1/4 the size. If K/2 is hotter, I know the answer is in K/4 .. K. Guess K/2-1 next. The two subcases are K/4 .. K/2-1 and K/2 .. K, both of which are nice. But it took me three guesses to (in the worst-case) halve the size of the problem; if I ever do this, I wind up doing lg N + 6 guesses.