Búsqueda binaria

La búsqueda binaria es como buscar una palabra en un diccionario: lo abres por la mitad, miras si la palabra va antes o después y repites con esa mitad. En una lista ordenada encuentra cualquier valor entre un millón en 20 comparaciones como máximo.

Una fila ordenada de barras con la barra central resaltada, la mitad de la fila atenuada y una línea discontinua a la altura del objetivo
Una fila ordenada de barras con la barra central resaltada, la mitad de la fila atenuada y una línea discontinua a la altura del objetivo

La idea

En una lista ordenada, una comparación te dice algo más que si has encontrado el objetivo: te dice en qué lado está. Compara el objetivo con el valor del centro. Si son iguales, has terminado. Si el valor central es menor, todo lo anterior también lo es, así que el objetivo solo puede estar después. Si es mayor, el objetivo solo puede estar antes. Quédate solo con esa mitad y repite.

Un ejemplo

Busca 23 en 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. El valor central es 16, que es menor, así que solo quedan de 23 a 91. Su centro es 56, que es mayor, así que solo quedan 23 y 38. Su centro es 23: encontrado en la posición 6 tras 3 comparaciones, donde la búsqueda lineal necesita 6. Buscar 40 en la misma lista compara 16, 56, 23 y 38, tras lo cual no queda nada: 4 comparaciones para saber que 40 no está, frente a 10 de la búsqueda lineal.

Dividir a la mitad rinde rápido

Tras una comparación queda como máximo la mitad de la lista, tras dos una cuarta parte, tras k como máximo unos n/2ᵏ. La búsqueda se detiene cuando no queda nada, así que necesita como máximo ⌊log₂ n⌋ + 1 comparaciones: 6 para 40 valores, 10 para 1000, 20 para un millón y 30 para mil millones. Duplicar la lista solo añade una comparación. Eso se escribe O(log n).

Fácil de describir, difícil de hacer bien

John Mauchly describió la búsqueda binaria en 1946, pero según Donald Knuth la primera versión que funcionaba para cualquier longitud de lista no se publicó hasta 1962. Más tarde, Jon Bentley vio que solo alrededor de uno de cada diez programadores profesionales la escribía bien: las condiciones de parada y el más o menos uno al partir las mitades son fáciles de equivocar. En 2006, Joshua Bloch mostró que la forma habitual de hallar el centro, (low + high) / 2, puede desbordarse con listas muy largas, un error que llevaba años en la biblioteca de Java. Escribir low + (high − low) / 2, como hace la app, lo evita.

John Mauchly (quinto por la izquierda) con otros responsables del ENIAC delante de la máquina, en una fotografía del Ejército de los Estados Unidos. Mauchly describió la búsqueda binaria en 1946.
John Mauchly (quinto por la izquierda) con otros responsables del ENIAC delante de la máquina, en una fotografía del Ejército de los Estados Unidos. Mauchly describió la búsqueda binaria en 1946.

Variantes y usos

Con duplicados, la búsqueda binaria encuentra una de las coincidencias; las versiones que siguen hacia la izquierda o la derecha encuentran la primera o la última, o la posición donde se insertaría un valor que falta. La misma idea de dividir a la mitad encuentra la raíz de una ecuación (bisección), la versión en la que apareció un error por primera vez (git bisect) y la respuesta a muchos problemas de optimización. Los árboles binarios de búsqueda guardan los datos para que cada consulta siga el mismo camino de mitades.

Pruébala

Abre la app, elige un valor en Buscar y pulsa Paso. La parte sombreada es donde aún puede estar el objetivo; el valor central está resaltado, y la mitad descartada se atenúa. Los recuadros muestran cuántos valores son aún posibles y cuántas comparaciones necesitaría una búsqueda lineal para el mismo valor. Busca un valor que falte, o usa 40 barras, para ver cómo crece la diferencia.

Preguntas frecuentes

¿Cuál es la complejidad temporal de la búsqueda binaria?

O(log n): como máximo ⌊log₂ n⌋ + 1 comparaciones para n valores. En el mejor caso basta una comparación, cuando el objetivo está en el centro. La versión iterativa necesita O(1) de memoria adicional.

¿Qué diferencia hay entre la búsqueda binaria y la búsqueda lineal?

La búsqueda lineal revisa los valores uno a uno y funciona con cualquier lista, pero puede necesitar n comparaciones. La búsqueda binaria solo funciona con una lista ordenada, pero descarta la mitad de lo que queda en cada comparación, así que necesita unas log₂ n.

¿Vale la pena ordenar una lista solo para usar la búsqueda binaria?

Solo si vas a buscar en ella muchas veces. Ordenar cuesta unos n log n pasos, más que una sola búsqueda lineal. Una vez ordenada la lista, cada búsqueda posterior es muy barata.

¿Sirve la búsqueda binaria para algo más que listas?

Sí, para cualquier cosa en la que una prueba te diga en qué lado de la respuesta estás: un rango de números, las versiones de un programa o los intentos en un juego de mayor o menor.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Prueba la búsqueda binaria