猜数字时仅知道所提议的数字是较低还是较高？

Question

我需要猜一个数字。我只能看到我建议的数字是较低还是较高。性能非常重要，因此我想到了以下算法：

假设我要猜测的数字是600。

• 我从数字1000开始（或者为了获得更高的性能，它是先前数字的平均结果）。

• 然后，我检查1000是否高于或低于600。

• 然后，我将数字除以2（现在是500），并检查它是否小于或大于600。它是否小于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