Way to Improve Binary Search when Search Space Changes

Question

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.

Answer 1

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.

Answer 2

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.