Vamos a jugar un pequeño juego para darte una idea de cómo diferentes algoritmos para el mismo problema pueden tener eficiencias tremendamente distintas. La computadora va a seleccionar aleatoriamente un entero entre 1 y 16. Tienes que adivinar el número al hacer intentos hasta que encuentres el número que escogió la computadora:
Una vez que hayas encontrado el número, dinos: ¿qué técnica usaste para decidir que número adivinar a continuación?
Tal vez adivinaste 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 adivinas 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 30, necesitarías 30 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 30, entonces en promedio necesitarías 15 intentos.
Pero podrías hacer algo más eficiente que intentar adivinar en secuencia 1, 2, 3, 4, …, ¿cierto? Gracias a que la computadora te dice si el intento es demasiado bajo, demasiado alto, o correcto, puedes empezar por adivinar que es el 15. Si el número que la computadora seleccionó es menor que 15, entonces como sabes que el 15 es demasiado alto, puedes eliminar todos los números del 15 al 30 de cualquier futuro intento de adivinar. Si el número seleccionado por la computadora es mayor que 15, entonces de igual manera puedes eliminar todos los números del 1 al 15 de cualquier futuro intento de adivinar. 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 30 haya seleccionado la computadora, con esta técnica deberías poder encontrar el número en a lo más 5 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.