Búsqueda exponencial

Búsqueda exponencial
Estructura de datos	Array
Clase de complejidad	Algoritmo de Búsqueda;
Tiempo de ejecución
Peor caso	O(log i)
Mejor caso	O(1)
Caso promedio	O(log i)
Complejidad espacial	O(1)
	[editar datos en Wikidata]

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.

Algoritmo

La búsqueda exponencial permite buscar a través de una lista no acotada ordenada para un valor de entrada especificado (la llave de búsqueda). El algoritmo consiste en dos etapas. 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 $2^{j}$ es más grande que la llave de búsqueda. Este valor, $2^{j}$ se convierte en el límite superior para la búsqueda binaria con el poder anterior de 2, $2^{j-1}$ , siendo el límite inferior para la búsqueda binaria.^[3]

// Devuelve la posición de la llave key en el array arr de tamaño size.
template <typename T>
int exponential_search(T arr[], int size, T key)
{
    if (size == 0) {
        return NOT_FOUND;
    }

    int bound = 1;
    while (bound < size && arr[bound] < key) {
        bound *= 2;
    }

    return binary_search(arr, key, bound/2, min(bound, size));
}

En cada paso, el algoritmo compara la llave de búsqueda con el valor en el índice de la búsqueda actual. 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, $2^{j-1}$ , y el índice de búsqueda actual, $2^{j}$ . La búsqueda binaria se ejecuta entonces con el resultado de un fracaso, si la llave de búsqueda no está en la lista, o la posición de la llave de búsqueda en la lista.

Rendimiento

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 $\lceil \log i\rceil$ veces. Como la lista está ordenada, después de doblar el índice de búsqueda $\lceil \log i\rceil$ veces, el algoritmo estará en un índice de búsqueda que es más grande que o igual que i cuando $2^{\lceil \log(i)\rceil }\geq i$ . 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. El tamaño de este intervalo sería $2^{j}-2^{j-1}$ donde, como se vio antes, j = log i. Esto significa que el tamaño del intervalo siendo explorado es $2^{\log i}-2^{\log i-1}=2^{\log i-1}$ . Esto nos da un tiempo de ejecución de $\log(2^{logi-1})=\log i-1=O(\log i)$ .

Esto le da al algoritmo un tiempo de ejecución total, calculado sumando los tiempos de las dos etapas, de $O(\log i)+O(\log i)=2O(\log i)=O(\log i)$ .

Alternativas

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. Esto divide la primera etapa del algoritmo a dos partes, haciendo el algoritmo un algoritmo de tres etapas en general. La primera etapa nueva determina un valor $j'$ , justo como antes, tal que $2^{j'}$ es mayor que la llave de búsqueda y $2^{j'/2}$ es menor que la llave de búsqueda. Anteriormente, $j'$ se determinaba de un modo unario calculando la potencia siguiente de 2 (i.e., añadiendo 1 a j). En la variación, se propone que $j'$ se doble en cambio (p. ej., saltando de $2^{2}$ a $2^{4}$ en vez de $2^{3}$ ). El primer $j'$ tal que $2^{j'}$ es mayor que la llave de búsqueda conforma un límite superior mucho más aproximado que antes. Una vez que este $j'$ sea encontrado, el algoritmo se mueve a su segunda etapa y una búsqueda binaria se ejecuta en el intervalo formado por $j'/2$ y $j'$ , 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 $2^{j-1}$ y $2^{j}$ , como antes. El rendimiento de esta variación es $\lfloor \log i\rfloor +2\lfloor \log(\lfloor \log i\rfloor +1)\rfloor +1=O(\log i)$

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.

También, una estructura de datos con una versión rigurosa de la propiedad de dedo dinámica puede ser dada cuando el resultado anterior de la búsqueda binaria k-anidada se utiliza en un array ordenado.^[4] Usando esta variación, el número de las comparaciones hechas durante una búsqueda es $\log d+\log \log d+...+O(\log *d)$ , donde d es la diferencia en rango entre el último elemento que fue accedido y el elemento actual siendo accedido.

Véase también

Referencias

↑ Baeza-Yates, Ricardo (2010). Tapio Elomaa, ed. Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday. Springer. pp. 45–61. ISBN 9783642124754.
↑ ^a ^b Bentley, Jon L. (1976). «An almost optimal algorithm for unbounded searching». Information Processing Letters 5 (3). ISSN 0020-0190.
↑ ^a ^b Jonsson, Håkan (19 de abril de 2011). «Exponential Binary Search». Archivado desde el original el 1 de junio de 2020. Consultado el 24 de marzo de 2014.
↑ Andersson, Arne (2007). «Dynamic ordered sets with exponential search trees». Journal of the ACM 54 (3). ISSN 0004-5411.

Datos: Q17012914

[BaezaYates-1] Baeza-Yates, Ricardo (2010). Tapio Elomaa, ed. Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday. Springer. pp. 45–61. ISBN 9783642124754.

[PaperBentley-2] Bentley, Jon L. (1976). «An almost optimal algorithm for unbounded searching». Information Processing Letters 5 (3). ISSN 0020-0190.

[NotesJonsson-3] Jonsson, Håkan (19 de abril de 2011). «Exponential Binary Search». Archivado desde el original el 1 de junio de 2020. Consultado el 24 de marzo de 2014.

[PaperAndersson-4] Andersson, Arne (2007). «Dynamic ordered sets with exponential search trees». Journal of the ACM 54 (3). ISSN 0004-5411.

[1]

[2]

[3]

[4]