猜测一个数字，仅知道所提议的数字是较低还是较高? [英] Guessing a number knowing only if the number proposed is lower or higher?

问题描述

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

I need to guess a number. I can only see if the number I'm proposing is lower or higher. Performance matters a whole lot, so I thought of the following algorithm:

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

Let's say the number I'm trying to guess is 600.

• 我从数字1000开始(或者为获得更高的性能，它是先前数字的平均结果).

• I start out with the number 1000 (or for even higher performance, the average result of previous numbers).

然后检查1000是否高于或低于600.

I then check if 1000 is higher or lower than 600. It is higher.

然后我将数字除以2(现在是500)，并检查它是小于还是大于600.它小于或小于600.

I then divide the number by 2 (so that it is now 500), and check if it is lower or higher than 600. It is lower.

然后我找到差异并将其除以2，以下列方式检索新的数字:((1000-500)/2).结果是750.然后检查该数字.

I then find the difference and divide it by 2 in the following way to retrieve a new number: ((1000 - 500) / 2). The result is 750. I then check that number.

以此类推.

这是最好的方法吗?有更聪明的方法吗?就我而言，每次猜测大约需要500毫秒，我需要在尽可能短的时间内猜测很多数字.

Is this the best approach? Is there a smarter way of doing this? For my case, every guess takes approximately 500 milliseconds, and I need to guess quite a lot of numbers in as low time as possible.

我可以粗略地认为先前猜测的平均结果也接近即将到来的数字，因此我可以利用其中的一种模式发挥自己的优势.

I can roughly assume that the average result of previous guesses is close to the upcoming numbers too, so there's a pattern there which I can use for my own advantage.

推荐答案

是binary search是执行此操作的最有效方法. Binary Search是您所描述的.对于1到N之间的数字，Binary Search在O(log(n))时间内运行.

yes binary search is the most effective way of doing this. Binary Search is what you described. For a number between 1 and N Binary Search runs in O(log(n)) time.

这是查找1-N之间数字的算法

So here is the algorithm to find a number between 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

这篇关于猜测一个数字，仅知道所提议的数字是较低还是较高?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！