Guessing a number knowing only if the number proposed is lower or higher?

Question

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:

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

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

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

• 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.

• 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.

And so on.

Is this the best approach or 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.

Answer 1

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.

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

Answer 2

Well, you're taking the best possible approach without the extra information - it's a binary search, basically.

Exactly how you use the "average result of previous guesses" is up to you; it would suggest biasing the results towards that average, but you'd need to perform analysis of just how indicative previous results are in order to work out the best approach. Don't just use the average: use the complete distribution.

For example, if all the results have been in the range 600-700 (even though the hypothetical range is up to 1000) with an average of 670, you might start with 670 but if it says "guess higher" then you would probably want to choose a value between 670 and 700 as your next guess, rather than 835 (which is very likely to be higher than the real result).

I suggest you log all the results from previous enquiries, so you can then use that as test data for alternative approaches.