En Ciencias de la Computación, una búsqueda exponencial (también llamado búsqueda galopante o búsqueda Struzik)[1] es un algoritmo, creado por Jon Bentley y Andrew Chi-Chih Yao en 1976, para buscar en listas infinitas/no acotadas ordenadas.
[2] Hay numerosas maneras para implementarlo siendo la más común determinar el rango en que la llave de búsqueda reside y realizar una búsqueda binaria dentro de dicho rango.
Esto demora O(log i) dónde i es la posición de la llave de búsqueda en la lista, si la llave de búsqueda está en la lista, o la posición donde la llave de búsqueda debería estar, si la llave de búsqueda no está en la lista.
La búsqueda exponencial también puede ser usada en listas acotadas.
La búsqueda exponencial puede incluso mejorar los tiempos de algoritmos de búsqueda en listas acotadas, como búsqueda binaria, cuando el elemento buscado está cerca del principio del array.
Esto es porque la búsqueda exponencial correrá en O(log i), donde i es el índice del elemento buscado en la lista, mientras que la búsqueda binaria correría en O(log n), donde n es el número de elementos en la lista.
La primera etapa determina un rango en el que la llave de búsqueda residiría si estuviese en la lista.
En la segunda etapa, se realiza una búsqueda binaria en ese rango.
En la primera etapa, suponiendo que la lista está ordenada en orden ascendente, el algoritmo busca el primer exponente j, donde el valor
es más grande que la llave de búsqueda.
se convierte en el límite superior para la búsqueda binaria con el poder anterior de 2,
Si el elemento en el índice actual es más pequeño que la llave de búsqueda, el algoritmo vuelve a ejecutarse, saltándose el siguiente índice de búsqueda doblándolo, calculando la siguiente potencia de 2.
[3] Si el elemento en el índice actual es mayor que la llave de búsqueda, el algoritmo ahora sabe que la llave de búsqueda, si está contenido en la lista en absoluto, está localizado en el intervalo formado por el índice de búsqueda anterior,
La primera etapa del algoritmo demora O(log i), donde i es el índice donde la llave de búsqueda estaría en la lista.
Esto es porque, para determinar el límite superior para la búsqueda binaria, el bucle se ejecuta exactamente
De esta forma, la primera etapa del algoritmo demora O(log i).
La segunda parte del algoritmo también demora O(log i).
Cuando la segunda etapa es sencillamente una búsqueda binaria, demora O(log n) donde n es el tamaño del intervalo donde se realizó la búsqueda.
donde, como se vio antes, j = log i.
Esto significa que el tamaño del intervalo siendo explorado es
Bentley y Yao sugirieron variaciones para el algoritmo de búsqueda exponencial.
[2] Estas variaciones constan de ejecutar una búsqueda binaria, en oposición a la búsqueda unaria, al determinar el límite superior para la búsqueda binaria en la segunda etapa del algoritmo.
es mayor que la llave de búsqueda y
es menor que la llave de búsqueda.
sea encontrado, el algoritmo se mueve a su segunda etapa y una búsqueda binaria se ejecuta en el intervalo formado por
, devolviendo el límite superior más preciso el exponente j. De ahí, la tercera etapa del algoritmo ejecuta la búsqueda binaria en el intervalo
Bentley y Yao generalizan esta variación a una donde cualquier número, k, de las búsquedas binarias se ejecuta durante la primera etapa del algoritmo, dando la k-anidada variación de búsqueda binaria.
La ejecución asintótica no cambia para las variaciones, corriendo en O(log i), como con el algoritmo de búsqueda exponencial original.
[4] Usando esta variación, el número de las comparaciones hechas durante una búsqueda es
, donde d es la diferencia en rango entre el último elemento que fue accedido y el elemento actual siendo accedido.