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.

Solution 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

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

Solution 3

In general, binary search starting at the middle point of the range is the optimal strategy. However, you have additional specific information which may make this a suboptimal strategy. This depends critically in what exactly "close to the average of the previous results" means.

If numbers are close to the previous average then dividing by 2 in the second step is not optimal.

Example: Previous numbers 630, 650, 620, 660. You start with 640.

Your number is actually closer. Imagine that it is 634.

The number is lower. If in the second step you divide by 2, you get 320, thus losing any advantage about the previous average numbers.

You should analyze the behaviour further. It may be optimal, in your specific case, to start at the mean of the N previous numbers and then add or substract some quantity related to the standard deviation of the previous numbers.

Solution 4

Yes, binary search (your algorithm) is correct here. However there is one thing missing in the standard binary search:

For binary search you normally need to know the maximum and minimum between which you are searching. In case you do not know this, you have to iteratively find the maximum in the beginning, like so:

• Start with zero
• if it is higher than the number searched, zero is your maximum and you have to find a minimum
• if it is lower than the number searched, zero is your minimum and you have to find a maximum
• You can search for your maximum/minimum by starting at 1 or -1 and always multiplying by two until you find a number which is greater/smaller

When you always multiply by two, you will be much faster than when you search linearly.

View more solutions