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

Question

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

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

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

• Then I check to see if it is over 1000 or less than 600. This is more.

• Then I divide the number by 2 (so now it is 500) and check if it is less than or higher than 600. It is less.

• Then I will find the difference and divide it by 2 as follows to get a new number: ((1000 - 500) / 2). The result is 750. Then I check this number.

Etc.

Is this a better approach? Is there a smarter way to do this? For my case, each guess takes about 500 milliseconds, and I need to guess quite a few numbers in the minimum amount of time.

I can roughly assume that the average result of previous guesses is close to the upcoming numbers, so there is a template there that I can use for my own advantages.

Answer 1

yes binary search is the most efficient way to do this. binary search is what you described. For a number from 1 to N binary search , O(log(n)) time is executed.

So, here is an algorithm for finding 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 take the best possible approach without additional information - this is binary search basically.

How you use the “average result of previous guesses” is up to you; this would suggest shifting the results to this average, but you would need to analyze how indicative the previous results are in order to work out the best approach. Don't just use the average: use the full distribution.

For example, if all the results were in the range of 600-700 (although the hypothetical range is up to 1000) with an average value of 670, you can start with 670, but if it says “guess higher,” then you probably want to choose a value between 670 and 700 as your next assumption, not 835 (which is likely to be higher than the actual result).

I suggest that you log all the results of previous queries, so you can use them as test data for alternative approaches.

Answer 3

In general, a binary search starting at the midpoint of a range is the optimal strategy. However, you have additional specific information that might make this suboptimal strategy. This critically depends on what it means "close to average compared to previous results."

If the numbers are close to the previous average, then dividing by 2 at the second stage is not optimal.

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

Your number is closer. Imagine this is 634.

The number is below. If in the second step you divide by 2, you get 320, thereby losing the edge over previous averages.

You should analyze the behavior further. In your particular case, it may be optimal to start with the average of N previous numbers, and then add or subtract some amount associated with the standard deviation previous numbers.

Answer 4

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

For binary searches, you usually need to know the maximum and minimum gaps between which you are looking. If you do not know this, you need to iteratively find the maximum at the beginning, for example:

• Start from scratch
• if it is greater than the desired number, zero is your maximum, and you need to find the minimum
• if it is less than the desired number, zero is your minimum, and you need to find the maximum
• You can search for the maximum / minimum value, starting from 1 or -1 and always multiplying by two, until you find a number that is more / less

When you always multiply by two, you will be much faster than with linear search.

Answer 5

Do you know the range of possible values? If so, always start in the middle and do what you describe.

Answer 6

A standard binary search between 0 and N (N is a given number) will give you an answer in logN mode.

Answer 7

 int a = 1, b = n+1, 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 

You have to add +1 to n, otherwise you can never get n, since it is int.