近似数查找算法
Algorithm for approximate number finding
考虑以下游戏：
- 约翰和彼得同意一个数字 n。
- 约翰在 1 和 n 之间选择了一个数字 x。
- Peter 在 1 和 n 之间进行了一系列的猜测 k。对于每个猜测：
- 如果x/2 ≤ k ≤ 2x，则彼得获胜。
- 否则，John 告诉 Peter x 是否小于 k.
Peter 想以最少的猜测次数获胜。
有明显的解决方案需要最坏情况 O(log n) 猜测，但一位朋友告诉我有一个解决方案比那更好的渐近行为。我朋友说的对吗？
你的朋友是对的。 x 的可能值可以划分为范围 {1,2,3,4}, {5,6,…,19,20}, {21,22,…, 83,84} 等，其中每个范围都有一个覆盖整个范围的 "central" 元素；例如，如果 x 介于 21 和 84 之间，则 k = 42 是一个获胜的猜测。有O(log n)这样的范围，Peter可以使用二分查找在O[=中找到合适的范围19=](log log n) 猜测。
考虑以下游戏：
- 约翰和彼得同意一个数字 n。
- 约翰在 1 和 n 之间选择了一个数字 x。
- Peter 在 1 和 n 之间进行了一系列的猜测 k。对于每个猜测：
- 如果x/2 ≤ k ≤ 2x，则彼得获胜。
- 否则，John 告诉 Peter x 是否小于 k.
Peter 想以最少的猜测次数获胜。
有明显的解决方案需要最坏情况 O(log n) 猜测，但一位朋友告诉我有一个解决方案比那更好的渐近行为。我朋友说的对吗？
你的朋友是对的。 x 的可能值可以划分为范围 {1,2,3,4}, {5,6,…,19,20}, {21,22,…, 83,84} 等，其中每个范围都有一个覆盖整个范围的 "central" 元素；例如，如果 x 介于 21 和 84 之间，则 k = 42 是一个获胜的猜测。有O(log n)这样的范围，Peter可以使用二分查找在O[=中找到合适的范围19=](log log n) 猜测。