Búsqueda binaria

La búsqueda binaria (binary search) es un método que permite buscar algo más rápido al partir el intervalo de búsqueda en dos. Su aplicación más común es buscar valores en arreglos ordenados; no obstante, la idea de partir el intervalo es crucial en muchas otras tareas típicas.

Búsqueda en arreglos ordenados

El problema más típico que conduce a la búsqueda binaria es el siguiente. Dado un arreglo ordenado $A_0 \leq A_1 \leq \dots \leq A_{n-1}$ , hay que comprobar si $k$ está presente en la secuencia. La solución más simple sería revisar cada elemento uno por uno y compararlo con $k$ (una llamada búsqueda lineal). Este enfoque funciona en $O(n)$ , pero no aprovecha el hecho de que el arreglo está ordenado.

Búsqueda binaria del valor $7$ en un arreglo.
La imagen de AlwaysAngry se distribuye bajo la licencia CC BY-SA 4.0 .

Supongamos ahora que conocemos dos índices $L < R$ tales que $A_L \leq k \leq A_R$ . Como el arreglo está ordenado, podemos deducir que $k$ o bien aparece entre $A_L, A_{L+1}, \dots, A_R$ o bien no aparece en el arreglo en absoluto. Si elegimos un índice arbitrario $M$ tal que $L < M < R$ y comprobamos si $k$ es menor o mayor que $A_M$ , tenemos dos casos posibles:

$A_L \leq k \leq A_M$ . En este caso, reducimos el problema de $[L, R]$ a $[L, M]$ ;
$A_M \leq k \leq A_R$ . En este caso, reducimos el problema de $[L, R]$ a $[M, R]$ .

Cuando no es posible elegir $M$ , es decir, cuando $R = L + 1$ , comparamos $k$ directamente con $A_L$ y $A_R$ . En caso contrario, querríamos elegir $M$ de modo que reduzca el segmento activo a un solo elemento lo más rápido posible en el peor caso.

En el peor caso siempre reduciremos al segmento más grande entre $[L, M]$ y $[M, R]$ . Así, en el peor caso la reducción sería de $R-L$ a $\max(M-L, R-M)$ . Para minimizar este valor, debemos elegir $M \approx \frac{L+R}{2}$ , y entonces

$M-L \approx \frac{R-L}{2} \approx R-M.$

En otras palabras, desde la perspectiva del peor caso es óptimo elegir siempre $M$ en el medio de $[L, R]$ y partirlo por la mitad. Así, el segmento activo se reduce a la mitad en cada paso hasta que queda de tamaño $1$ . Por lo tanto, si el proceso necesita $h$ pasos, al final reduce la diferencia entre $R$ y $L$ de $R-L$ a $\frac{R-L}{2^h} \approx 1$ , lo que nos da la ecuación $2^h \approx R-L$ .

Tomando $\log_2$ en ambos lados, obtenemos $h \approx \log_2(R-L) \in O(\log n)$ .

Un número logarítmico de pasos es drásticamente mejor que el de la búsqueda lineal. Por ejemplo, para $n \approx 2^{20} \approx 10^6$ harían falta aproximadamente un millón de operaciones con búsqueda lineal, pero solo alrededor de $20$ operaciones con la búsqueda binaria.

Lower bound y upper bound

A menudo conviene hallar la posición del primer elemento que es mayor o igual que $k$ (llamada lower bound o cota inferior de $k$ en el arreglo) o la posición del primer elemento que es estrictamente mayor que $k$ (llamada upper bound o cota superior de $k$ ), en lugar de la posición exacta del elemento.

Juntas, la lower bound y la upper bound producen un semiintervalo, posiblemente vacío, de los elementos del arreglo que son iguales a $k$ . Para comprobar si $k$ está presente en el arreglo basta hallar su lower bound y verificar si el elemento correspondiente es igual a $k$ .

Implementación

La explicación anterior da una descripción aproximada del algoritmo. Para los detalles de implementación necesitamos ser más precisos.

Mantendremos un par $L < R$ tal que $A_L \leq k < A_R$ . Esto significa que el intervalo activo de búsqueda es $[L, R)$ . Usamos un semiintervalo en lugar de un segmento $[L, R]$ porque resulta requerir menos trabajo con casos borde.

Cuando $R = L+1$ , de las definiciones anteriores se deduce que $R$ es la upper bound de $k$ . Es conveniente inicializar $R$ con el índice past-the-end (uno más allá del final), es decir $R=n$ , y $L$ con el índice anterior al comienzo, es decir $L=-1$ . Esto está bien mientras nunca evaluemos $A_L$ ni $A_R$ de forma directa en el algoritmo, tratándolos formalmente como $A_L = -\infty$ y $A_R = +\infty$ .

Por último, para concretar el valor de $M$ que elegimos, nos quedaremos con $M = \lfloor \frac{L+R}{2} \rfloor$ .

Entonces la implementación podría verse así:


... // un arreglo ordenado está guardado como a[0], a[1], ..., a[n-1]
int l = -1, r = n;
while (r - l > 1) {
    int m = (l + r) / 2;
    if (k < a[m]) {
        r = m; // a[l] <= k < a[m] <= a[r]
    } else {
        l = m; // a[l] <= a[m] <= k < a[r]
    }
}

Durante la ejecución del algoritmo nunca evaluamos $A_L$ ni $A_R$ , ya que $L < M < R$ . Al final, $L$ será el índice del último elemento que no es mayor que $k$ (o $-1$ si no existe tal elemento) y $R$ será el índice del primer elemento mayor que $k$ (o $n$ si no existe tal elemento).

Nota. Calcular m como m = (r + l) / 2 puede provocar desbordamiento si l y r son dos enteros positivos, y este error vivió unos 9 años en el JDK, como se describe en el blogpost . Algunos enfoques alternativos incluyen, por ejemplo, escribir m = l + (r - l) / 2, que siempre funciona para enteros positivos l y r, pero aún puede desbordar si l es un número negativo. Si se usa C++20, ofrece una solución alternativa en la forma m = std::midpoint(l, r), que siempre funciona correctamente.

Búsqueda sobre un predicado arbitrario

Sea $f : {0,1,\dots, n-1} \to {0, 1}$ una función booleana definida en $0,1,\dots,n-1$ que es monótona creciente, es decir

$f(0) \leq f(1) \leq \dots \leq f(n-1).$

La búsqueda binaria, tal como se describió arriba, halla la partición del arreglo según el predicado $f(M)$ , que guarda el valor booleano de la expresión $k < A_M$ . Es posible usar un predicado monótono arbitrario en lugar de $k < A_M$ . Resulta particularmente útil cuando el cálculo de $f(k)$ requiere demasiado tiempo como para computarlo para cada valor posible. En otras palabras, la búsqueda binaria halla el único índice $L$ tal que $f(L) = 0$ y $f(R)=f(L+1)=1$ si existe tal punto de transición, o nos da $L = n-1$ si $f(0) = \dots = f(n-1) = 0$ o $L = -1$ si $f(0) = \dots = f(n-1) = 1$ .

Demostración de corrección suponiendo que existe un punto de transición, es decir $f(0)=0$ y $f(n-1)=1$ : la implementación mantiene el invariante del bucle $f(l)=0, f(r)=1$ . Cuando $r - l > 1$ , la elección de $m$ implica que $r-l$ siempre decrece. El bucle termina cuando $r - l = 1$ , lo que nos da el punto de transición deseado.


... // f(i) es una función booleana tal que f(0) <= ... <= f(n-1)
int l = -1, r = n;
while (r - l > 1) {
    int m = (l + r) / 2;
    if (f(m)) {
        r = m; // 0 = f(l) < f(m) = 1
    } else {
        l = m; // 0 = f(m) < f(r) = 1
    }
}

Búsqueda binaria sobre la respuesta

Esta situación ocurre a menudo cuando se nos pide calcular algún valor, pero solo somos capaces de comprobar si ese valor es al menos $i$ . Por ejemplo, se nos da un arreglo $a_1,\dots,a_n$ y se nos pide hallar el máximo promedio entero (floored average)

$\left \lfloor \frac{a_l + a_{l+1} + \dots + a_r}{r-l+1} \right\rfloor$

entre todos los pares posibles $l,r$ tales que $r-l \geq x$ . Una de las formas simples de resolver este problema es comprobar si la respuesta es al menos $\lambda$ , es decir, si existe un par $l, r$ tal que se cumple lo siguiente:

$\frac{a_l + a_{l+1} + \dots + a_r}{r-l+1} \geq \lambda.$

De forma equivalente, se reescribe como

$(a_l - \lambda) + (a_{l+1} - \lambda) + \dots + (a_r - \lambda) \geq 0,$

de modo que ahora hay que comprobar si existe un subarreglo del nuevo arreglo $a_i - \lambda$ de longitud al menos $x+1$ con suma no negativa, lo cual se puede hacer con algunas sumas de prefijos.

Búsqueda continua

Sea $f : \mathbb R \to \mathbb R$ una función real continua en un segmento $[L, R]$ .

Sin pérdida de generalidad, supongamos que $f(L) \leq f(R)$ . Del teorema del valor intermedio se sigue que para cualquier $y \in [f(L), f(R)]$ existe $x \in [L, R]$ tal que $f(x) = y$ . Nótese que, a diferencia de los párrafos anteriores, no se exige que la función sea monótona.

El valor $x$ puede aproximarse hasta $\pm\delta$ en tiempo $O\left(\log \frac{R-L}{\delta}\right)$ para cualquier valor específico de $\delta$ . La idea es esencialmente la misma: si tomamos $M \in (L, R)$ , podremos reducir el intervalo de búsqueda a $[L, M]$ o a $[M, R]$ según si $f(M)$ es mayor que $y$ . Un ejemplo común aquí sería hallar raíces de polinomios de grado impar.

Por ejemplo, sea $f(x)=x^3 + ax^2 + bx + c$ . Entonces $f(L) \to -\infty$ y $f(R) \to +\infty$ cuando $L \to -\infty$ y $R \to +\infty$ . Esto significa que siempre es posible hallar un $L$ suficientemente pequeño y un $R$ suficientemente grande tales que $f(L) < 0$ y $f(R) > 0$ . Entonces, con búsqueda binaria es posible hallar un intervalo arbitrariamente pequeño que contenga un $x$ tal que $f(x)=0$ .

Búsqueda con potencias de 2

Otra forma destacable de hacer búsqueda binaria es, en lugar de mantener un segmento activo, mantener el puntero actual $i$ y la potencia actual $k$ . El puntero empieza en $i=L$ y luego, en cada iteración, se evalúa el predicado en el punto $i+2^k$ . Si el predicado sigue siendo $0$ , el puntero avanza de $i$ a $i+2^k$ ; en caso contrario se queda igual, y después la potencia $k$ se disminuye en $1$ .

Este paradigma se usa mucho en tareas sobre árboles, como hallar el ancestro común más bajo (LCA) de dos vértices o hallar un ancestro de un vértice específico que tenga cierta altura. También se puede adaptar, por ejemplo, para hallar el $k$ -ésimo elemento no nulo en un Árbol de Fenwick.