我需要猜一个数字。我只能看看我提议的数字是更低还是更高。性能非常重要，所以我想到了以下算法：
假设我要猜测的数字是 600。
-
我从数字 1000 开始（或者为了获得更高的性能，使用之前数字的平均结果）。
-
然后我检查 1000 是否高于或低于 600。它更高。
-
然后我将这个数字除以 2（现在是 500），并检查它是否低于或高于 600。它较低。
-
然后我找到差值并按以下方式除以 2 以检索新数字：(1000 + 500) / 2。结果是 750。然后我检查该数字。
等等。
这是最好的方法还是有更明智的方法？就我而言，每次猜测大约需要 500 毫秒，并且我需要在尽可能短的时间内猜测相当多的数字。
我可以粗略地假设之前猜测的平均结果也接近即将到来的数字，因此我可以利用其中的一种模式来为自己带来优势。
yes binary search是最有效的方法。Binary Search就是你所描述的。对于 1 到 N 之间的数字Binary Search跑进O(log(n)) time.
这是查找 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
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
