1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Consider that numbers as 1/3 (=$0.\overline{01}$ in binary) will make the computer choose forever if $\epsilon \rightarrow 0$ $\endgroup$ – Blex Jun 24 '15 at 21:31
  • $\begingroup$ How can I see that more rigorously? It seems intuitive I suppose. $\endgroup$ – user217285 Jun 24 '15 at 21:32
  • 2
    $\begingroup$ I'm not sure I understand, what is the data set? Is it all of [0,1]?if so it is infinite so we need to talk about that, binary search is defined for a finite collection. Also, it seems like you're thinking of searching in [0,1] with this method of eliminating halves of the interval each time, you can consider the binary representation of a number to estimate the number of steps needed for such a method $\endgroup$ – Belgi Jun 24 '15 at 21:34
  • $\begingroup$ Not too familiar with exact terminology -- I've heard it called bisection search before too. But yes the universal set is $[0,1]$. Are there any good links on the internet to read more about how the binary representation could help? $\endgroup$ – user217285 Jun 24 '15 at 21:36
  • 1
    $\begingroup$ When the computer makes a choice it selects the $n$-th digit in binary representation on the $n$-th iteration until it replicates the number you have given. So the idea to fool the computer is to make the selection process the longest as possible choosing numbers with long alternating binary representation. $\endgroup$ – Blex Jun 24 '15 at 21:51
0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.