近似数发现算法

Question

考虑以下游戏:

• 约翰和彼得同意一个数字n.
• 约翰选择1和n之间的数字x.
• 彼得提出了一系列猜测ķ 1和之间Ñ.对于每个猜测:
  • 如果X/2≤  ķ  ≤2 X,然后彼得获胜.
  • 否则,约翰告诉彼得x是否小于k.

彼得希望以最少的猜测获胜.

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

Answer 1

你的朋友是对的.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)猜测中找到正确的范围.