algorithm - 近似数查找算法

Question

考虑以下游戏：

• 约翰和彼得就数字n达成一致。
• John在 1 和n之间选择一个数字x。
• Peter在 1 和n之间进行了一系列猜测k。对于每个猜测：
  • 如果x /2 ≤  k  ≤ 2 x，则彼得获胜。
  • 否则，约翰告诉彼得x是否小于k。

彼得希望以最少的猜测次数获胜。

有明显的解决方案需要最坏情况O (log  n ) 的猜测，但一位朋友告诉我，有一个解决方案的渐近行为比这更好。我朋友说的对吗？

标签： algorithmsearchlogarithm

Answer 1

你的朋友是对的。x的可能值可以划分为 {1,2,3,4}、{5,6,...,19,20}、{21,22,...,83,84} 等范围，其中每个range 有一个覆盖整个范围的“中心”元素；例如，如果x介于 21 和 84 之间，则k  = 42 是一个获胜的猜测。有O (log  n ) 个这样的范围，Peter 可以使用二进制搜索在O (log log  n ) 猜测中找到正确的范围。