我需要猜一个数字。我只能看看我提议的数字是更低还是更高。性能非常重要,所以我想到了以下算法:
假设我要猜的数字是 600。
我从数字 1000 开始(或者为了获得更高的性能,使用之前数字的平均结果)。
然后我检查 1000 是高于还是低于 600。它更高。
然后我将该数字除以 2(现在为 500),并检查它是低于还是高于 600。它较低。
然后我找到差值并按以下方式将其除以 2 以检索新数字:(1000 + 500)/2。结果为 750。然后我检查该数字。
等等。
这是最好的方法还是有更聪明的方法?对于我的情况,每次猜测大约需要 500 毫秒,我需要在尽可能短的时间内猜出相当多的数字。
我可以粗略地假设之前猜测的平均结果也接近于即将到来的数字,所以这里有一个模式,我可以利用它来发挥自己的优势。
最佳答案
是的二进制搜索
是最有效的方法。 Binary Search
就是您所描述的。对于介于 1 和 N 之间的数字,二进制搜索
在 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
关于algorithm - 猜一个数字只知道建议的数字是更低还是更高?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9605110/