Worst case binary search

Question

Suppose you play a game with a computer program where you guess a number between 0 and 1 and the computer uses binary search to search for your number.

My question is what is the best number to pick to maximize the time it takes for the computer to search for it?

Clearly there's a lot of symmetry here, so I imagine there would be a several points that are the best to pick. Assume the search is finished when the difference between the computer guess and the number is less than $\varepsilon = 0.001$. Will the set be dense as $\varepsilon \to 0$?

So far the only thing I can think of is staying "one step ahead" of the computer. For example, my guess will be 0.25, so the computer will find it in 2 guesses, but then I'll change my guess to $\frac{0.25+0.50}{2}$, but that will be found in 3 guesses, and so on and so forth.

Answer 1

You have to formulate your problem more rigorously since it's not clear how a binary search could land on an irrational number like $e$ or $\pi$. But here's a hint for the idea you're working with:

For example, my guess will be 0.25, so the computer will find it in 2 guesses, but then I'll change my guess to 0.25+0.502, but that will be found in 3 guesses, and so on and so forth.

That's a sequence. Take its limit. What do you get?

Answer 2

What sort of numbers are you selecting? If you agree to use $n$ bit unsigned integers you are just trying to avoid the few that the computer will use for the search. For example, if $n=10$ the range is $0-1023$ Presumably the computer's first guess will be $511$ or $512$ so those are poor choices. If you say lower, the next choice will be $255$ or $256$, and so on. You probably want the last couple bits to be different, because all these end in all $0$'s or $1$'s but otherwise it doesn't matter much. It is hard to guarantee that the computer will need all $10$ guesses, but making sure it needs at least $9$ shouldn't be too hard as the first $8$ can only account for $2^8-1=255$ of the numbers.

If you can use repeating decimals, the computer will always guess a dyadic fraction, so pick $1/3$ and you are safe.