algorithm - 冷热二进制搜索游戏

Question

热或冷。

我认为您必须进行某种二分查找，但我不确定该怎么做。

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.

我绞尽脑汁，似乎想不出一个 lg N + O(1)。

我找到了这个:http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1316188034但看不懂图表，也没有描述其他可能的情况。

Answer 1

假设您知道您的 secret 整数在 [a,b] 中, 你最后的猜测是 c .

您想将间隔除以二，并知道您的 secret 整数是否位于 [a,m] 之间或 [m,b] , 与 m=(a+b)/2 .

诀窍是猜测d , 这样 (c+d)/2 = (a+b)/2 .

不失一般性，我们可以假设 d大于c .然后，如果d比 c 热，你的 secret 整数将大于 (c+d)/2 = (a+b)/2 = m , 所以你的 secret 整数将位于 [m,b] .如果d比c凉爽，你的 secret 整数将属于 [a,m] .

您需要能够在 -N 之间进行猜测和 2N因为你不能保证 c和 d如上定义将始终为 [a,b] .你的两个第一个猜测可以是 1和 N .

因此，您将每次猜测的区间除以 2，因此复杂度为 log(N) + O(1)。

一个简短的例子来说明这一点(随机选择的结果):

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

---

编辑，@tmyklebu 建议:

我们还需要证明我们的猜测总是落在[-N,2N]之间。

通过递归，假设c (我们之前的猜测)在 [a-(a+b), b+(a+b)] = [-b,a+2b] 中

然后 d = a+b-c <= a+b-(-b) <= a+2b和 d = a+b-c >= a+b-(a+2b) >= -b

初始案例:a=1, b=N, c=1 , c确实在[-b,a+2*b]

QED