This question is inspired by a question posed about a Number Searching "game" on Stack Overflow. In essence, the premise of the game is to find a randomly chosen number between 1..N (where N in this case was 1000). A normal application of a binary search would result in O(logN) steps (see binary search complexity), or 8 steps on average.
However, the twist in the games was that if the "guessed" number was lower than the chosen number, then the chosen number would be increased by a random amount. (Note: this is some confusion as to whether the amount of the random increase was random on each change or was a constant for a given run).
So, if the initial chosen number was 623, and the first guess was 500 (standard mid-point in a binary search between upper and lower bound), then the chosen number would increase by some random amount (say 42; thus the new chosen number would be 665). The potential upper bound would then need to be adjusted by the potential range of the additional random number (in the case of the game, it was 200). Thus after this first initial incorrect guess, the search space went from 1..1000 to 500..1200.
Using 100,000 runs and a random increase on each low guess, the average steps to converge on the chosen number was about 128. I lack the math skills to develop a proof, and this was a pure empirical observation (and the total runs is now closer to 1m).
I would think that logically it would be better to be biased towards guessing high and working down rather than guessing low and therefore changing the number again.
I tried a few different (and likely naive) approaches towards biasing towards the high end, but at best they provided no demonstrable improvement (and in some cases clearly created regression in the solution).
Is there a mathematical approach that could shed insight into how to adjust the binary search when the search space is changing?
Edit: try to outline some attempts.
I first tried adjusting so the next guess would change from using the standard
guess = (lowerBound + upperBound) / 2;
to pushing it upwards as
guess = Math.min( (lowerBound + 200 + upperBound) / 2), upperBound);
The idea was that the next guess should be higher (thus avoiding a potential double low guess). The average affect was an increase of 39 steps. Using 100 (which is 1/2 of the available range) was a bit better, and using 50 resulted in a single step reduction (maybe), but there is zero rationale behind changing these numbers. It might be the case that varying this number based upon the total remaining search space would be useful, but here a bit of math insight would be helpful rather than just guessing.
A comment on the Guessing Game question suggested trying to implement a "risk" approach
double risc = 100.0/(upperBound-lowerBound);
if (risc <= 1) {
guess = (upperBound + lowerBound) /2;
}
else {
guess = upperBound - Math.max((int)((upperBound - lowerBound)/risc/2),1);
}
This approach appears to reduce on average from 128 to 127 steps, but a single step savings is not significant nor necessarily repeatable.
There were a couple of other things I tried, but all within the same basic structure. There could be more advanced formulations of the search of which I am unaware. And it is truly a binary search, not an attempt to build a tree or anything.
count=1000000, sum=128130745, min=1, average=128.130745, max=1821
. This example used a random increase of 1-200 on an incorrect low guess, the standard adjustment where theupperBound
was adjusted by 200 in order to encapsulate the maximum change of the variable, the lower bound was set to the guess, and the next guess was set to(lowerBound + upperBound) / 2
. If it doesn't converge, I've not seen it, but I suppose it it theoretically possible. $\endgroup$