Vamos a jugar un juego para darte una idea de cómo los diferentes algoritmos para el mismo problema puede tener eficiencias muy diferentes. La computadora va a seleccionar un número entero entre 1 y 16 de manera aleatoria. Tu vas a seguir intentando números hasta encontrar el número de la computadora y, cada vez, la computadora te dirá 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 esta manera la llamamos búsqueda lineal, porque intentas todos los números como si estuvieran alineados en una fila. Funcionaría. ¿Pero cuál es el mayor número de intentos que podrías necesitar? Si la computadora selecciona 16, necesitarías 16 intentos. Ahora, podrías tener mucha suerte, que sería el caso cuando la computadora seleccionara 1 y encontraras el número en el primer intento. ¿Qué tal en promedio? Si la computadora tiene la misma probabilidad de escoger cualquier número entre 1 y 16, entonces en promedio necesitarías 8 intentos.
Pero podrías hacer algo más eficiente que intentar los números en secuencia 1, 2, 3, 4, …, ¿cierto? Como la computadora te dice si el intento es demasiado bajo, demasiado alto, o correcto, puedes empezar por intentar con el 8. Si el número que la computadora seleccionó es menor que 8, entonces como sabes que el 8 es demasiado alto, puedes eliminar todos los números del 8 al 16 de cualquier futuro intento. Si el número seleccionado por la computadora es mayor que 8, entonces de igual manera puedes eliminar todos los números del 1 al 7. De cualquier manera, puedes eliminar aproximadamente la mitad de los números. En tu siguiente intento, elimina la mitad de los números restantes. Sigue de esta manera, siempre eliminando la mitad de los números restantes. A esta manera de reducir a la mitad la llamamos búsqueda binaria, y no importa qué número del 1 al 16 haya seleccionado la computadora, con esta técnica deberías poder encontrar el número en a lo más 4 intentos.
Mira, inténtalo para un número del 1 al 300. Deberías necesitar no 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.
Cargando