只知道提议的数字是低还是高,猜测一个数字？

Question

我需要猜一个数字.我只能看看我提议的数字是低还是高.性能很重要,所以我想到了以下算法:

假设我想猜的数字是600.

• 我从数字1000(或更高的性能,以前的数字的平均结果)开始.

• 然后检查1000是高于还是低于600.它更高.

• 然后我将数字除以2(现在为500),并检查它是否低于或高于600.它更低.

• 然后我找到差异并按以下方式将其除以2以检索新数字:((1000 - 500)/ 2).结果是750.然后检查那个号码.

等等.

这是最好的方法吗？有更聪明的方法吗？对于我的情况,每次猜测大约需要500毫秒,我需要在尽可能短的时间内猜测很多数字.

我可以粗略地假设先前猜测的平均结果也接近即将到来的数字,因此有一种模式可供我自己使用.

Answer 1

是的,这binary search是最有效的方法.Binary Search就是你所描述的.对于1到N之间的数字及时Binary Search运行O(log(n)).

所以这里是找到1-N之间的数字的算法

int a = 1, b = n, guess = average of previous answers;

while(guess is wrong) {

    if(guess lower than answer) {a = guess;}
    else if(guess higher than answer) {b = guess;}

    guess = (a+b)/2;

} //Go back to while