近似数查找算法

Question

考虑以下游戏:

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

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

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

Answer 1

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