Búsqueda binaria — algoritmo, complejidad temporal y código

La búsqueda binaria es una forma rápida de encontrar un valor objetivo en una lista ordenada. Revisas el elemento central, descartas la mitad de los valores restantes y repites. Si la lista no está ordenada, esa lógica deja de ser válida.

En una lista ascendente, la regla es simple: si el valor central es menor que el objetivo, buscas a la derecha; si es mayor, buscas a la izquierda. Como el rango se sigue reduciendo aproximadamente a la mitad, la búsqueda binaria se ejecuta en tiempo $O(\log n)$.

Cómo funciona la búsqueda binaria en una lista ordenada

Usa esta lista ordenada:

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

Supón que el objetivo es $31$.

Empieza con el rango completo. El valor central es $24$. Como $31 > 24$, todo lo que está a la izquierda de $24$ puede descartarse, así que la búsqueda continúa en

$$[31, 39, 45, 52]$$

Ahora el valor central es $39$. Como $31 < 39$, todo lo que está a la derecha de $39$ puede descartarse, así que el rango pasa a ser

$$[31]$$

Ahora el valor central es $31$, así que la búsqueda se detiene. La idea útil no es solo que se encontró el objetivo. En dos comparaciones, el rango candidato pasó de $9$ valores a $1$.

Por qué la búsqueda binaria es $O(\log n)$

Cada comparación elimina aproximadamente la mitad de los candidatos restantes. Después de un paso, quedan aproximadamente $n/2$ elementos. Después de dos pasos, quedan aproximadamente $n/4$. Después de $k$ pasos, el tamaño restante es aproximadamente

$$\frac{n}{2^k}$$

La búsqueda termina cuando esa cantidad es aproximadamente $1$, así que el número de pasos cumple

$$2^k \approx n$$

Tomando $\log_2$ en ambos lados, obtenemos

$$k \approx \log_2 n$$

Por eso la búsqueda binaria escala bien. Una búsqueda lineal puede necesitar hasta $n$ comprobaciones, pero la búsqueda binaria solo necesita suficientes comprobaciones para seguir dividiendo el rango a la mitad.

Ejemplo de código de búsqueda binaria

Aquí tienes una versión iterativa estándar en Python: