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

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

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

num = low

应该:

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

这是最快的方式,它被称为二分搜索.