1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm interested to know what you tried, if you care to share. $\endgroup$ – law-of-fives May 4 '17 at 20:40
  • $\begingroup$ @law-of-fives, you want me to share my pathetic attempts? OK, I'll update the question with some of them. But just keep the laughing to a minimum... :) $\endgroup$ – KevinO May 4 '17 at 20:43
  • $\begingroup$ Thanks @KevinO I had considered something different from you, always trying to under-guess to push the value up. After all, an increased lower bound is always informative; but, because the background number may increase randomly, previous over-estimates provide very little information. Sorry I can't be of actual help here :/ $\endgroup$ – law-of-fives May 4 '17 at 21:28
  • $\begingroup$ I am not convinced this process is guaranteed to converge. If the original number is the top of the range you will eventually get to guessing less than $100$ below the top of the range. Then if the addition is $200$ you will have a range of $200-300$ and guess $100-150$ below the top. The range increases again and you never get there. If the increases are small, after a low guess you will get a number of high ones and lower the ceiling. $\endgroup$ – Ross Millikan May 4 '17 at 22:05
  • $\begingroup$ @RossMillikan, In a test of 1,000,000 runs, the the number of steps to converge were: 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 the upperBound 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$ – KevinO May 5 '17 at 1:35
0
$\begingroup$

Some thoughts too long to comment. I would suggest a strategy where you try to determine the increase along with finding the number. I will just use parameters to describe it, but they need to be adjusted. Start by guessing a high number, say $900$. Keep decreasing in units of $100$ until you guess low. Now you know the original number within a range of $100$. You know the current number within a range of $300$. Again guess down from the top in $50$s. If you find it is more than $100$ above the past limit you know the increment exceeds $100$ and you can just put that minimum into your calculations. Clearly this takes some fleshing out.

$\endgroup$
  • $\begingroup$ I will attempt to implement such an algorithm and see what happens. I'll have to change the code to be a state machine, so it's not a 5 minute task :). Thank you for the suggestion! $\endgroup$ – KevinO May 5 '17 at 2:28
0
$\begingroup$

Let $w$ be the width of the original search space, and $p$ the penalty for guessing too low. Picking a number at offset $n$ from the beginning results in search spaces of sizes $n-1$ (if guess is too high) and $w - n - 1 + p$ if the guess is too low. The optimal pick should equalize those sizes, that is $n = \dfrac{w + p}{2}$, and the size of new search space is $\dfrac{w + p}{2} - 1$.

Obviously, the resulting sequence of sizes converges to $p-2$. Once it's been reached, it is not possible to divide the space anymore, and you'd have to switch to linear search.

$\endgroup$
  • $\begingroup$ This would be reasonable if we were trying to maximize the worst-case search time. It seems like the question is asking for the average-case search time (if the original number and the penalty are both random) and in this case it's not clear to me that equalizing the search spaces is optimal. $\endgroup$ – Misha Lavrov May 5 '17 at 0:06
  • $\begingroup$ @MishaLavrov The actual penalty is random indeed, but since we don't know it, we must increase the search space by the maximal possible penalty. Probably I should clarify this. $\endgroup$ – user58697 May 5 '17 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.