En este artículo, se discute un uso avanzado de la búsqueda binaria, para una situación muy particular. Es requisito entender bien la búsqueda binaria usual. Las ideas desarrolladas pueden servir también en otros problemas.
La búsqueda binaria “común” sirve para encontrar el “corte” en una propiedad binaria. Es decir, si tenemos una función $f$ monótona, que a cada entero le asigna un valor binario $0$ o $1$, búsqueda binaria sirve para encontrar el primer 1.
La situación que sea plantea aquí corresponde a encontrar los hasta $K-1$ posibles “cortes” de una función $K$-aria, es decir, que toma valores enteros en el rango $[0,K)$. Una manera de dar los cortes sería por ejemplo, dar el menor valor de $x$ tal que $f(x) \geq 1$, el menor valor de $x$ tal que $f(x) \geq 2$, y así hasta $K-1$, que es el máximo posible.
Siempre podemos recorrer todos los $N$ valores de $x$ para buscar en una pasada todos los $K$ puntos de corte. Esto toma $O(N)$ evaluaciones de la función.
En adelante, asumiremos siempre que $N$, la cantidad posible de valores de $x$, es bastante mayor que $K$, pues sino no hay nada considerablemente mejor que este barrido exhaustivo.
Una solución razonable para este problema es utilizar búsqueda binaria para encontrar cada uno de los cortes, de manera totalmente independiente. Es decir, se ejecutaría $K-1$ veces el algoritmo usual de búsqueda binaria sobre todo el rango posible de $N$ valores: Una para buscar el corte de los $1$, otra para el corte de los $2$, y así siguiendo. Cada una es una consulta usual de lower_bound, con su correspondiente valor.
Como cada búsqueda binaria tiene un costo $O(\lg N)$, el costo total en peor caso es $O(K \lg N)$. Esta cota es ajustada, pues es posible dar ejemplos donde se examinan esa cantidad de valores de la función con este algoritmo.
En lugar de realizar búsquedas independientes, podemos utilizar los resultados de búsquedas anteriores, y tratar de ir generando los cortes incrementalmente. Concretamente, si ya identificamos el primer $x$ tal que $f(x) = 1$, necesariamente el primer $2$ deberá estar después, así que podemos tomar como inicio del rango de la búsqueda binaria este valor de $x$.
Esta optimización sin embargo no cambia la complejidad asintótica en peor caso.
Se puede obtener una mejora importante observando un caso “malo” para la idea anterior, y tratando de evitar el problema que surge.
Un claro caso malo para la idea anterior, sería que todas las búsquedas binarias operen sobre un rango muy grande, es decir, que la optimización casi no logre reducir el tamaño de los rangos buscados. Para que esto ocurra, casi todas las fronteras estarán muy cerca entre sí, de modo que “saltar” a la siguiente presente muy poco ahorro. Entonces, el problema a subsanar es que si el corte se encuentra muy cerca del comienzo, igual nuestra búsqueda binaria siempre tarda $\lg N$ pasos hasta llegar allí, porque siempre comienza por el medio.
Una manera de subsanar esto es comenzar siempre desde el principio del rango, pero probando sucesivamente “saltos” de tamaños potencia de 2, cada vez más grandes. Es decir, si $a+1$ es la posición “base” donde encontramos el corte anterior (de modo que sabemos que el corte de este paso está más adelante que $a$), comenzamos evaluando $f$ en las posiciones $a+1$, $a+2$, $a+4$, $a+8$, $a+16$, y así siguiendo hasta que alguna cumpla $f(x) \geq t$, siendo $t$ el valor que buscamos para el corte actual1).
Luego, sabremos que el corte debe aparecer dentro del último “salto”, y podemos buscarlo allí con una búsqueda binaria usual: por ejemplo, si $f(a+8) < t$, pero $f(a+16) \geq t$, descubrimos que el corte está entre $a+8$ y $a+16$, así que allí lo buscamos con búsqueda binaria.
Se puede ver que el total de pasos para encontrar el primer valor $f(x) \geq t$ con este método es $O(\lg(x_t - x_{t-1}))$, es decir, como si hiciéramos búsqueda binaria solamente entre este corte y el anterior. La razón es que la segunda búsqueda binaria opera sobre un rango que no es más grande que esto, así que hace esa cantidad de pasos, y en la primera etapa al realizar saltos de tamaño exponencial la cantidad total de saltos es siempre logarítmica en la distancia recorrida.
En base a la cota anterior, al sumar el costo de ir encontrando todos los cortes desde el primero hasta el último se obtiene una complejidad $O\left(K \lg \left(\frac{N}{K} \right) \right)$: el peor caso se da ahora cuando los cortes están bien distribuidos, de modo que las distancias entre ellos son aproximadamente iguales.
Se puede obtener una solución con mejor constante, pero la misma complejidad asintótica, utilizando un algoritmo recursivo.
La idea motivadora es intentar preguntar siempre por el elemento central. Ya habíamos visto al estudiar la búsqueda binaria, que examinar siempre el elemento central era una excelente idea porque, en el peor caso, permitía descartar la mayor cantidad posible de opciones en una sola pregunta. Algo muy similar ocurre en esta variante del problema: intuitivamente, preguntar muy cerca del borde es una mala idea, pues ganamos poca información (si preguntamos por el primer elemento por ejemplo y resulta ser $f(0) = 0$, el problema restante es completamente idéntico pero con tamaño $N-1$, y utilizar una pregunta entera para reducir el tamaño únicamente en $1$ es evidentemente demasiado poco).
Entonces, lo que haremos en esta versión del algoritmo será siempre preguntar por el elemento central. La idea quizás es menos clara ahora, pues en lugar de ir incrementalmente “corte por corte”, para aprovechar siempre toda la información que tenemos y no repetir preguntas innecesarias, lo que conviene es calcular todos los cortes en la misma función recursiva.
Supongamos por ejemplo, que tenemos $K=10$ y comenzamos consultando el elemento central, y es $f(c) = 7$. ¿Qué nos dice esto? Nos dice inmediatamente que las primeras apariciones de $8$ y $9$ estarán a la derecha de $c$, mientras que las primeras apariciones de $0$,$1$,$2$,$\dots$,$7$ estarán entre $0$ y $c$ inclusive. En otras palabras, el rango de $10$ cortes a analizar que teníamos se nos separa en dos: 8 cortes deben ser analizados del lado izquierdo, y 2 cortes deben ser analizados del lado derecho. Lo que hacemos es, recursivamente, analizar cada una de estas mitades de la misma forma, pero sabiendo que allí la función solamente puede tomar valores en un subrango de los $K$ posibles valores totales.
Supongamos que analizamos el caso derecho, por ejemplo: Allí, sabemos que la función solo puede tomar valores $7$, $8$ y $9$, y nos interesa descubrir la primera aparición de $8$ y de $9$ (la primera de 7 no, porque sabemos que apareció antes, ya que una llamada recursiva “nos llamó” habiendo descubierto un valor $7$ a nuestra izquierda). Preguntamos como siempre en la mitad de nuestro rango: ¿Qué pasaría si encontramos un $7$? Sabríamos inmediatamente que la mitad izquierda no sirve para nada, y podemos ignorarla quedando solamente con la mitad derecha, y los mismos valores posibles $7,8,9$. Es decir, en tal caso reducimos el problema a la mitad. Lo mismo hubiera ocurrido si hubiéramos encontrado un $9$: La mitad derecha resultaría inútil, y en la izquierda seguiríamos buscando los mismos dos cortes.
En resumen, si continuamos con este proceso, el problema o bien se reduce a la mitad en cada paso, o bien se parte en dos partes el rango de valores que buscamos, generando dos problemas independientes con rangos diferentes. El caso base ocurre cuando se vacía el rango a buscar, y en ese caso encontramos un “salto” de la función entre valores consecutivos de $x$. Podemos allí mismo anotar o procesar entonces ese salto, ya que eso era lo que buscábamos.
Se puede calcular con cuidado el tamaño del árbol de recursión, y demostrar que este enfoque realiza aproximadamente $K \lg \left( \frac{N}{K} \right )$ evaluaciones.
En la siguiente sección se puede ver una implementación de esta idea, y ahí se puede ver que este enfoque recursivo queda realmente muy corto y elegante. En todo momento, la función recursiva tomará un rango de valores de $x$, y un rango de cortes buscados. Todo esto puede representarse muy cómodamente con 4 parámetros a,b,fA,fB, que indican que sabemos que $f(a) = \mbox{fA}$, $f(b) = \mbox{fB}$, y que debemos investigar la región entre medio de $a$ y $b$.
En una corrida comparativa de estos dos algoritmos eficientes, se obtuvieron los siguientes resultados:
Para N=10000000 y K=1000 Evaluaciones con saltos exponenciales : 25846 Evaluaciones con algoritmo recursivo : 13429 Valor teorico : 13287.7 Algoritmo directo : 23230.2
El “valor teórico” $K \lg \left( \frac{N}{K} \right )$ en estos ejemplos da un valor extremadamente cercano a lo que obtiene el método recursivo.
Notar que los algoritmos “directos” que hacen $K-1$ búsquedas binarias superarían en este caso al algoritmo de saltos exponenciales. Esto tiene sentido ya que cuando $K$ no es demasiado grande, realizar todas las búsquedas binarias individuales no es comparativamente tan malo.
Para una corrida con valores de $K$ más extremos tendremos:
Para N=10000000 y K=100000 Evaluaciones con saltos exponenciales : 1271222 Evaluaciones con algoritmo recursivo : 682974 Valor teorico : 664385.62 Algoritmo directo : 2325326.41
Si bien la versión recursiva eficiente sigue utilizando aproximadamente la mitad de evaluaciones que la de saltos exponenciales, con estos valores grandes de $K$ la de saltos exponenciales ya supera claramente a la evaluación directa, a diferencia de lo que ocurrió en el otro ejemplo con un $K$ más pequeño.
El código utilizado, que implementa y compara ambos algoritmos sobre un caso al azar, es el siguiente:
#include <iostream> #include <vector> #include <cassert> #include <algorithm> #include <iomanip> using namespace std; const int N = 10000000; const int K = 100000; vector<int> f(K-1); // "Evalua la f", es llamada por los algoritmos. int ef(int x) { auto it = lower_bound(f.begin(), f.end(), x); return int(it - f.begin()); } vector<int> resultadoExponenciales(K-1); vector<int> resultadoRecursivo(K-1); int saltosExponenciales() { int total = 0; int prev = -1; for (int t=1;t<=K-1;t++) { int delta = 1; int a = prev; total++; while (prev+delta < N && ef(prev+delta) < t) { total++; a = prev+delta; delta *= 2; } int b = min(N, prev+delta); while (b-a > 1) { int c = (a+b)/2; total++; if (ef(c) >= t) b = c; else a = c; } resultadoExponenciales[t-1] = b; prev = b-1; } return total; } int recu(int a,int b, int fA, int fB) { assert(a < b); assert(fA <= fB); if (fA == fB) return 0; if (b-a == 1) { for (int t=fA+1; t <= fB; t++) resultadoRecursivo[t-1] = b; return 0; } else { int c = (a+b)/2; int fC = ef(c); return 1 + recu(a,c,fA, fC) + recu(c,b,fC,fB); } } int main() { for (int i=0;i<K-1;i++) f[i] = int((double(rand()) / double(RAND_MAX)) * N + 0.5); sort(f.begin(), f.end()); cout << "Para N=" << N << " y K=" << K << endl; cout << "Evaluaciones con saltos exponenciales : " << saltosExponenciales() << endl; cout << "Evaluaciones con algoritmo recursivo : " << recu(-1,N,0,K-1) << endl; cout << "Valor teorico : " << fixed << setprecision(2) << K*log(double(N)/double(K))/log(2.0) << endl; cout << "Algoritmo directo : " << fixed << setprecision(2) << (K-1)*log(double(N))/log(2.0) << endl; assert(resultadoExponenciales == resultadoRecursivo); return 0; }
Vemos que como muchas veces ocurre, la implementación que resulta más eficiente es también la más corta, simple y elegante. Lo difícil es formular y entender con claridad las ideas del algoritmo recursivo.
Si bien el impacto en el tiempo de ejecución es pequeño, hay varias razones más allá de eso para que nos importe. Las más importantes son:
Estas ideas pueden utilizarse para resolver exitosamente el problema El Gran Premio, de la IOI 2017.
Otro problema relacionado con estas ideas es Aliens, de la IOI 2007.