Búsqueda exponencial

La búsqueda binaria necesita saber dónde termina la lista antes de mirar en el medio. La búsqueda exponencial no: avanza al galope con pasos cada vez mayores hasta pasarse del valor buscado, y luego aplica búsqueda binaria al último paso. Por eso es ideal para listas de longitud desconocida, y rápida para valores cercanos al principio.

Una fila ordenada de barras con saltos que duplican su longitud sobre las posiciones 1, 2, 4 y 8, y el tramo entre los dos últimos saltos sombreado
Una fila ordenada de barras con saltos que duplican su longitud sobre las posiciones 1, 2, 4 y 8, y el tramo entre los dos últimos saltos sombreado

La idea

Revisa el valor de la posición 1, luego la 2, 4, 8, 16 y así sucesivamente, cada posición el doble de la anterior. Mientras el valor allí sea menor que el valor buscado, este tiene que estar más adelante. La primera vez que un valor no es menor, el valor buscado queda atrapado: está después de la posición revisada antes y no más allá de esta. Ese tramo está ordenado, así que una búsqueda binaria encuentra el valor buscado o muestra que no está.

Un ejemplo

Busca 23 en 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. La posición 1 tiene 2, la posición 2 tiene 5, la posición 4 tiene 12, todos menores. La posición 8 tiene 56, que es mayor, así que 23 solo puede estar en las posiciones 5 a 7. La búsqueda binaria revisa la del medio, la posición 6, y encuentra 23: 5 comparaciones, donde la búsqueda binaria simple necesita 3. Buscar 12 en la misma lista termina en la posición 4 tras 3 comparaciones, una menos que la búsqueda binaria, y 2 se encuentra en la posición 1 con una sola comparación.

Cuántas comparaciones

Para un valor en la posición i, la duplicación se detiene tras unos log₂ i pasos y deja un tramo de menos de i posiciones, que la búsqueda binaria cubre en unos log₂ i más. Así que la búsqueda cuesta unas 2 log₂ i comparaciones, sea cual sea la longitud de la lista. Cuando el valor buscado está cerca del principio, eso supera a la búsqueda binaria, que siempre paga unas log₂ n. Cuando está cerca del final, la búsqueda exponencial paga hasta el doble, aproximadamente. Con 40 valores, la aplicación hace de media unas 3 comparaciones para las cinco primeras posiciones y unas 9 para las cinco últimas, frente a unas 4,6 de la búsqueda binaria.

Longitud desconocida y galope

Jon Bentley y Andrew Yao describieron esta estrategia de duplicación en 1976 para la búsqueda no acotada: encontrar un valor en una secuencia ordenada sin final conocido, como una lista infinita o un flujo que solo se puede sondear. La misma idea acelera la fusión. Cuando una de dos secuencias ordenadas no deja de ganar, Timsort pasa al modo galope: mira 1, 2, 4, 8 posiciones por delante en la otra secuencia para encontrar dónde va el siguiente valor, en lugar de avanzar de posición en posición.

Pruébala

Abre la aplicación, elige un valor en Buscar y pulsa Paso. Cada consulta a las posiciones 1, 2, 4, 8 y así sucesivamente se resalta; en cuanto un valor no es menor, el tramo entre las dos últimas posiciones se sombrea y la búsqueda binaria toma el relevo. Busca un valor pequeño y luego uno grande, y compara el recuento con el recuadro de la búsqueda binaria.

Preguntas frecuentes

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

O(log i) para un valor en la posición i, así que como mucho O(log n) para una lista de n valores. Necesita O(1) de memoria adicional y una lista ordenada.

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

La búsqueda binaria empieza con la lista entera y necesita su longitud. La búsqueda exponencial primero encuentra, duplicando, un tramo que contiene el valor buscado, y luego aplica búsqueda binaria solo a ese tramo. Es más rápida cuando el valor buscado está cerca del principio y funciona sin conocer la longitud.

¿Por qué duplicar el paso y no sumar una cantidad fija?

Sumar un paso fijo es la búsqueda por saltos, que para recorrer la lista hace unas n dividido entre el paso consultas. Duplicando se llega a la posición i en unas log₂ i consultas, y el tramo que queda nunca es más del doble de lo necesario, así que la búsqueda binaria posterior sigue siendo corta.

¿Dónde se usa la búsqueda exponencial?

Al buscar en datos ordenados ilimitados o muy largos, al fusionar secuencias ordenadas (el galope de Timsort) y al buscar la primera posición en la que se cumple una condición cuando no se conoce un límite superior.

¿Listo para probarlo?

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

Prueba la búsqueda exponencial