# Search for the (slowly moving) number with penalty for too high test value

You task is to design a search algorithm that will find my secret number, which is between 0 and 2^64. If your test value is too low you can test again in 1 second. If your test value is too high you are not allowed to test again the next 300 seconds.

Every second I will add 1 to or subtract 1 from the number. I will not tell you what I have done, and while it may be random it also might not be random.

How can you find the approximate number fast?

The obvious answer is to use a binary search, but since the penalty is high for guessing too high, I would think it needs some adjustment.

Background

I need to find the speed of a system. The speed changes slowly. It takes 1 second to do a guess. If my guess is too low: no problem. If it is too high, then system reboots, causing a 5 minute delay.

My goal is to get a decent estimate of the speed relatively fast.

• guess at 1/300 in the possible range – ratchet freak Apr 10 '14 at 19:56
• Binary search from the small end. Somewhat related to en.wikipedia.org/wiki/Exponential_backoff Try 1, 2, 4, 8, 16, 32 ... until hit first "too high". Then switch to binary search between the last-known good value. – rwong Apr 10 '14 at 20:07
• While algorithms are on-topic, guessing games are not. Please edit your question to make it more clear what you need to understand the algorithm behind solving this puzzle. – user53019 Apr 10 '14 at 20:07

## 2 Answers

I did some empirical simulation of a simplified version of this system. It seems intuitive that one could use a binary search, modified with a weight factor to bias the "midpoint" selection toward lower numbers. Another answer proposed 300 (so choosing a midpoint that is 1/300 of the way from the left to the right), but I wanted to check this.

I wrote a simulation (code here) which runs 1000 trials for each weighting factor between 2 (standard binary search taking the midpoint at 1/2) and 499 (taking the midpoint at 1/499). The results can be seen in this spreadsheet, and the resulting graph looks something like this: What this appears to show is that a standard binary search does perform badly, as expected. However, the optimal weight factor appears to be something around 70 (so choosing the midpoint for the binary search as 1/70 of the way from the left to the right bound). (I'm not sure why this is true, perhaps a question for https://math.stackexchange.com.)

I did not attempt to model the target "wandering" behaviour in your question. You may modify the simulation to add this feature.

I am not a statistician, but it seems to me that guessing 1/300 of the overall range would get you the answer most quickly, a weighted binary search.

So, the first guess is (1/300) * 2^64

The second guess is either

on success (1/300) * (1/300) * 2^64 or

on failure (1/300) + (1/300) * (2^64 - (1/300))

etc.

• I was curious about this (seemingly sensible) idea, so I ran a simulation. See my answer for some simulation data. – Greg Hewgill Apr 10 '14 at 20:48