# Q：冷二进制搜索游戏

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.

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.

answer1： 回答1：

For numbers between (1~N):

1st guess: (1/3)N

2nd guess: (2/3)N -> tells us the answer is either in 1~(1/2)N or (1/2)N +1 ~ N

3rd guess: in 1~(1/2)N: try (1/6)N; in (1/2)N +1 ~ N: try (5/6)N

...

Starting from 2nd guess, each step cuts the range in 1/2. So it's step 1 + lgN

answer2： 回答2：

This is a repost of my answer at Hot or Cold Guess Secret Number, which unfortunately has no upvoted or accepted answer:

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.

answer3： 回答3：

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

``````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
.        .            .               .
.        .            .               .
.        .            .               .
``````

answer4： 回答4：

The solution is close to binary search. At each step you have an interval that the number can be in. Start with the whole interval [1, N]. First guess both ends - that is the numbers 1 and N. One of them will be closer, thus you will know that now the number you are searching for is in [1, N/2] or in [N/2 + 1, N](considering N even for simplicity). Now you go to the next step having a twice smaller interval. Continue using the same approach. Keep in mind that you've already probed one of the ends, however it may not be your last guess.

I am not sure what you mean by lg N + O(1), but the approach I suggest will perform O(log(N)) operations and in the worst case it will do exactly log4(N) probes.

algorithm  binary-search