猜测一个数字的最快方法只知道它是高于还是低于之前的猜测？

Question

我正在尝试解决一个问题，我必须猜测 1 到 2 * 10^9 之间的数字，只知道它是高于还是低于我之前的猜测。

现在我有一个适用于所有情况的代码，但它超过了仅为 31 的猜测限制。

status = ""
high = 2000000000
low = 1
num = low
print num
while 1:
    status= raw_input()
    if status== "OK":
        break
    elif status == "Higher":
        low = num
    elif status == "Lower":
        high = num
    num = int((high+low)/2)
    print num

我正在做的是从最小的数字开始作为我的第一个猜测，然后根据响应重新设置低值和高值。

你能帮我找到更快的方法吗？

Answer 1

您正在使用最佳算法。除了（编辑以说明 Jonathan 的评论）：您最初的猜测尽可能糟糕。将初始猜测设为 int((low+high)/2)。这将使循环次数减少 1。

你正在做的是二分查找。如果你想猜的数字真的是随机的，那你就不能做得更好了。

想想如果您每次都没有猜中点会发生什么。当您猜测一侧的值多于另一侧时，您要查找的数字更有可能位于值更多的一侧。所以大多数时候你消除的值不到一半。因此，经常您会有更难解决的问题。如果每次取中点，则每次都将值的数量减半。如果你取一些其他值，那么平均你还剩下一半以上。

所以我建议的唯一改变是从
开始
num = int((high+low)/2)

值得考虑使用

(high+low)//2

而不是调用 int。这个 returns 一个整数，不管你使用的是 python 2 还是 3: (high+low)/2 在 python.
的两个版本中会有不同的行为

Answer 2

将您的起始位置更改为范围的中间位置：

num = low

应该是：

num = int((low + high) / 2)

这是最快的方法，称为 binary search。

猜测一个数字的最快方法只知道它是高于还是低于之前的猜测？

Fastest way to guess a number only knowing if it is higher or lower than the previous guess?

python