Búsqueda binaria en el peor de los casos

Question

Supongamos que juegas a un juego con un programa informático en el que adivinas un número entre 0 y 1 y el ordenador utiliza la búsqueda binaria para buscar tu número.

Mi pregunta es ¿cuál es el mejor número a elegir para maximizar el tiempo que tarda el ordenador en buscarlo?

Está claro que aquí hay mucha simetría, así que imagino que habría varios puntos que son los mejores para elegir. Supongamos que la búsqueda se termina cuando la diferencia entre la conjetura del ordenador y el número es menor que $\varepsilon = 0.001$ . ¿El conjunto será denso como $\varepsilon \to 0$ ?

Hasta ahora lo único que se me ocurre es ir "un paso por delante" del ordenador. Por ejemplo, mi suposición será 0,25, por lo que el ordenador lo encontrará en 2 suposiciones, pero entonces voy a cambiar mi suposición a $\frac{0.25+0.50}{2}$ pero que se encontrará en 3 conjeturas, y así sucesivamente.

Answer 1

Tienes que formular tu problema de forma más rigurosa, ya que no está claro cómo una búsqueda binaria podría dar con un número irracional como $e$ o $\pi$ . Pero aquí tienes una pista para la idea con la que estás trabajando:

Por ejemplo, si adivino 0,25, el ordenador lo encontrará en 2 intentos, pero si cambio a 0,25+0,502, el ordenador lo encontrará en 3 intentos, y así sucesivamente.

Es una secuencia. Toma su límite. ¿Qué obtienes?

Answer 2

¿Qué tipo de números está seleccionando? Si acepta utilizar $n$ enteros sin signo de bits sólo está tratando de evitar los pocos que el ordenador utilizará para la búsqueda. Por ejemplo, si $n=10$ la gama es $0-1023$ Presumiblemente la primera suposición del ordenador será $511$ o $512$ así que esas son malas elecciones. Si dices más bajo, la siguiente opción será $255$ o $256$ etc. Es probable que desee que el último par de bits sean diferentes, porque todos estos terminan en todos $0$ o $1$ pero por lo demás no importa mucho. Es difícil garantizar que el ordenador necesitará todos los $10$ conjeturas, pero asegurándose de que necesita al menos $9$ no debería ser tan difícil como la primera $8$ sólo puede dar cuenta de $2^8-1=255$ de los números.

Si puedes usar decimales repetidos, el ordenador siempre adivinará una fracción diádica, así que elige $1/3$ y estás a salvo.