<分区>
当我们只想猜一个数字时，问题就很简单了。例如，我们想猜测 x 并且我们知道最大可能值是 n。可以进行二分查找，复杂度为O(log n)。
但是，我发现了这个问题的变体:
给定 0 假设猜测的是z，我们可以让提问者与另一个值进行比较，他会说出z与另一个值的关系——即小于、等于或大于。可能的比较是:
在我看来，我们可以只对 (x+y) 进行二分查找。因此，时间复杂度为 O(log(m+n))。这比找到 x，然后找到 y 更好，其复杂度为 O(log m + log n) = O(log mn) 但是，我很好奇是否有比在 x+y 上进行二分查找更好的解决方案。 非常感谢您的帮助。 编辑:
所以提问者首先想到的是数字x，还有数字y，然后他问回答者x+y的值是多少。如上所示，回答者可以提出三个问题。我的问题是回答者如何以最少的查询次数找到答案。
(1)比较x，和z。
(2)比较y，z。
(3)比较x+y和z。
最佳答案
当每种可能性具有相等概率时，二分搜索是最优的。 x 和 y 都是这种情况，但 x+y 不是这种情况。平均得到最少猜测的策略类似于但不完全是二分搜索。
通过二分查找，所有的可能性都是等概率的
probability | |
| [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] |
|_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
我们猜测中间值，并丢弃一半可能的答案:
probability | V X X X X X X X X X |
| [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] |
|_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
所有剩余的答案仍然是等概率的，所以我们可以简单地递归。
当找到 x+y 时，其中 x 和 y 都是从统一概率范围内随机选择的，每个 x+y 的概率不是等概率的。
probability | V |
| [] |
| [] [] [] |
| [] [] [] [] [] |
| [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] [] [] |
|____[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
显然，猜中间仍然是最好的第一个猜测:
probability | V X X X X X X X |
| [] |
| [] [] [] |
| [] [] [] [] [] |
| [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] |
| [] [] [] [] [] [] [] [] [] [] [] [] [] |
|____[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_[]_|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
但不直观的是接下来要猜测的地方。在上图中，8 之后的最佳猜测是 5 或 6(不是 4)，但我不确定如何准确计算。如果我弄清楚了，我会通知您。
v = lower_bound
u = upper_bound
t = probability(v)
s = probability(u)
r = min(s,t)
p = guess
(p-v)r+(p-v)^2/2 = (u-p)r+(u-p)^2/2
pr-rv+(p^2-pv+v^2)/2 = ur-pr+(u^2-up+p^2)/2
2pr-2rv+p^2-pv+v^2 = 2ur-2pr+u^2-up+p^2
2pr-2rv+p^2-pv+v^2-2pr+up-p^2 = 2ur+u^2
2pr+p^2-pv-2pr+up-p^2 = 2ur+u^2+2rv-v^2
-pv+up = 2ur+u^2+2rv-v^2
(u-v)p = u^2+2ur+2rv-v^2
p = (u^2+2ur+2rv-v^2)/(u-v)
不，那也是错误的。仍在努力。
[Niklas B. 观察到此答案中的所有内容都假定 x 和 y 均从其范围内均匀选取。如果这不是一个安全的假设，那么是的，二分查找平均最快]
关于algorithm - 猜测 x+y 值的最佳方法是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21895810/