Un juego de adivinar

Juguemos un juego para darte una idea de cómo diferentes algoritmos para el mismo problema pueden tener eficiencias muy diferentes. La computadora seleccionará aleatoriamente un número entero entre 1 y 15. Tu seguirás adivinando números hasta encontrar el número de la computadora, y la computadora te dirá cada vez si tu intento es demasiado alto o demasiado bajo:

Una vez que hayas encontrado el número, reflexiona acerca de qué técnica usaste al decidir qué número intentar a continuación.

Tal vez intentaste 1, luego 2, luego 3, luego 4, y así sucesivamente, hasta que adivinaste el número correcto. A este proceso lo llamamos búsqueda lineal, pues intentas todos los números como si estuvieran alineados en una fila. Funciona, ¿pero cuál es el mayor número de intentos que puedes requerir? Si la computadora selecciona 15, necesitarás 15 intentos. Aunque podrías tener mucha suerte, que es el caso cuando la computadora seleccionara 1 y encontraras el número en el primer intento. ¿Y en promedio? Si la computadora tiene la misma probabilidad de escoger cualquier número entre 1 y 15, entonces en promedio necesitas 8 intentos.

Pero puedes hacer algo más eficiente que solo adivinar 1, 2, 3, 4, … ¿cierto? Como la computadora te dice si un intento es demasiado bajo, demasiado alto, o correcto, puedes empezar en 8. Si el número que la computadora seleccionó es menor que 8, entonces, como sabes que el 8 es demasiado alto, puedes eliminar y ya no considerar todos los números del 8 al 15. Si el número seleccionado por la computadora es mayor que 8, entonces de igual manera puedes eliminar los números del 1 al 8. En cualquier caso puedes eliminar la mitad de los números. En tu siguiente intento, elimina la mitad de los números restantes. Sigue así, siempre eliminando la mitad de los números restantes.

A este proceso de reducir a la mitad lo llamamos búsqueda binaria, y sin importar qué número del 1 al 15 haya seleccionado la computadora, con esta técnica debes poder encontrar el número en no más 4 intentos.

Mira, inténtalo para un número del 1 al 300. No deberías necesitar más de 9 intentos.

¿Cuantos intentos te tomó encontrar el número esta vez? ¿Por qué nunca deberías necesitar más de 9 intentos (¿Puedes pensar en alguna explicación matemática?)

Regresaremos a la búsqueda binaria, y veremos cómo puedes usarla para buscar de manera eficiente un elemento en un arreglo de JavaScript. Pero primero, echemos un vistazo a un algoritmo para un problema más complicado.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.