Búsqueda exponencial

En informática , una búsqueda exponencial (también llamada búsqueda duplicada o búsqueda galopante o búsqueda de Struzik ) ^[1] es un algoritmo , creado por Jon Bentley y Andrew Chi-Chih Yao en 1976, para buscar listas ordenadas, ilimitadas/infinitas. ^[2] Hay numerosas formas de implementar esto, siendo la más común determinar un rango en el que reside la clave de búsqueda y realizar una búsqueda binaria dentro de ese rango. Esto toma O (log i ) donde i es la posición de la clave de búsqueda en la lista, si la clave de búsqueda está en la lista, o la posición donde debería estar la clave de búsqueda, si la clave de búsqueda no está en la lista.

La búsqueda exponencial también se puede utilizar para buscar en listas limitadas. La búsqueda exponencial puede incluso superar a las búsquedas más tradicionales para listas limitadas, como la búsqueda binaria, cuando el elemento que se busca está cerca del comienzo de la matriz. Esto se debe a que la búsqueda exponencial se ejecutará en tiempo O (log i ), donde i es el índice del elemento que se busca en la lista, mientras que la búsqueda binaria se ejecutaría en tiempo O (log n ), donde n es el número de elementos en la lista.

Algoritmo

La búsqueda exponencial permite buscar en una lista ordenada y sin límites un valor de entrada específico (la "clave" de búsqueda). El algoritmo consta de dos etapas. La primera etapa determina un rango en el que se encontraría la clave de búsqueda si estuviera en la lista. En la segunda etapa, se realiza una búsqueda binaria en este 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 mayor que la clave de búsqueda. Este valor, 2 ^j, se convierte en el límite superior de la búsqueda binaria, siendo la potencia anterior de 2, 2 ^{j - 1} , el límite inferior de la búsqueda binaria. ^[3]

// Devuelve la posición de la clave en la matriz arr de longitud size. template < typename T > int exponential_search ( T arr [], int size , T key ) { if ( size == 0 ) { return NOT_FOUND ; }                 int límite = 1 ; mientras ( límite < tamaño && arr [ límite ] < clave ) { límite *= 2 ; }                 devolver binary_search ( arr , clave , límite / 2 , min ( límite , tamaño )); }

En cada paso, el algoritmo compara el valor de la clave de búsqueda con el valor de la clave en el índice de búsqueda actual. Si el elemento en el índice actual es más pequeño que la clave de búsqueda, el algoritmo repite el proceso, saltando al siguiente índice de búsqueda duplicándolo, calculando la siguiente potencia de 2. ^[3] Si el elemento en el índice actual es más grande que la clave de búsqueda, el algoritmo ahora sabe que la clave de búsqueda, si está contenida en la lista, está ubicada en el intervalo formado por el índice de búsqueda anterior, 2 ^{j - 1} , y el índice de búsqueda actual, 2 ^j . Luego se realiza la búsqueda binaria con el resultado de un error, si la clave de búsqueda no está en la lista, o la posición de la clave de búsqueda en la lista.

Actuación

La primera etapa del algoritmo toma O (log i ) tiempo, donde i es el índice donde estaría la clave de búsqueda en la lista. Esto se debe a que, al determinar el límite superior para la búsqueda binaria, el bucle while se ejecuta exactamente veces. Dado que la lista está ordenada, después de duplicar el índice de búsqueda veces, el algoritmo estará en un índice de búsqueda que es mayor o igual a i como . Como tal, la primera etapa del algoritmo toma O (log i ) tiempo. $\lceil \log(i)\rceil$ $\lceil \log(i)\rceil$ $2^{\lceil \log(i)\rceil }\geq i$

La segunda parte del algoritmo también toma un tiempo de O (log i ). Como la segunda etapa es simplemente una búsqueda binaria, toma O (log n ) donde n es el tamaño del intervalo que se está buscando. El tamaño de este intervalo sería 2 ^j - 2 ^{j - 1} donde, como se vio anteriormente, j = log i . Esto significa que el tamaño del intervalo que se está buscando es 2 ^{log i} - 2 ^{log i - 1} = 2 ^{log i - 1} . Esto nos da un tiempo de ejecución de log (2 ^{log i - 1} ) = log ( i ) - 1 = O (log i ).

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

Alternativas

Bentley y Yao sugirieron varias variaciones para la búsqueda exponencial. ^[2] Estas variaciones consisten en realizar una búsqueda binaria, en lugar de una 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 en dos partes, lo que hace que el algoritmo sea un algoritmo de tres etapas en general. La nueva primera etapa determina un valor , al igual que antes, tal que es mayor que la clave de búsqueda y es menor que la clave de búsqueda. Anteriormente, se determinaba de manera unaria calculando la siguiente potencia de 2 (es decir, sumando 1 a j ). En la variación, se propone que se duplique en su lugar (por ejemplo, saltando de 2 ² a 2 ⁴ en lugar de 2 ³ ). El primer tal que es mayor que la clave de búsqueda forma un límite superior mucho más aproximado que antes. Una vez que se encuentra esto, el algoritmo pasa a su segunda etapa y se realiza una búsqueda binaria en el intervalo formado por y , dando el exponente de límite superior más preciso j . A partir de aquí, la tercera etapa del algoritmo realiza la búsqueda binaria en el intervalo 2 ^j^{- 1} y 2 ^j , como antes. El rendimiento de esta variación es = O (log i ). ${\estilo de visualización j'}$ ${\estilo de visualización 2^{j'}}$ $2^{j'/2}$ ${\estilo de visualización j'}$ ${\estilo de visualización j'}$ ${\estilo de visualización j'}$ ${\estilo de visualización 2^{j'}}$ ${\estilo de visualización j'}$ ${\estilo de visualización j'/2}$ ${\estilo de visualización j'}$ $\lpiso \log i\rpiso +2\lpiso \log(\lpiso \log i\rpiso +1)\rpiso +1$

Bentley y Yao generalizan esta variación en una en la que se realiza cualquier número, k , de búsquedas binarias durante la primera etapa del algoritmo, lo que da como resultado la variación de búsqueda binaria anidada en k . El tiempo de ejecución asintótico no cambia para las variaciones, ya que se ejecuta en tiempo O (log i ), como con el algoritmo de búsqueda exponencial original.

Además, se puede obtener una estructura de datos con una versión estricta de la propiedad de dedo dinámico cuando se utiliza el resultado anterior de la búsqueda binaria anidada en k en una matriz ordenada. ^[4] Usando esto, el número de comparaciones realizadas durante una búsqueda es log ( d ) + log log ( d ) + ... + O (log ^*d ), donde d es la diferencia de rango entre el último elemento al que se accedió y el elemento actual al que se accede.

Aplicaciones

Un algoritmo basado en el aumento exponencial de la banda de búsqueda resuelve la alineación global por pares para O(ns) , donde n es la longitud de las secuencias y s es la distancia de edición entre ellas. ^[5]^[6]

Véase también

Referencias

^ Baeza-Yates, Ricardo ; Salinger, Alejandro (2010), "Algoritmos de intersección rápida para secuencias ordenadas", en Elomaa, Tapio; Mannila, Heikki ; Orponen, Pekka (eds.), Algoritmos y aplicaciones: ensayos dedicados a Esko Ukkonen con motivo de su 60 cumpleaños , Lecture Notes in Computer Science, vol. 6060, Springer, pp. 45–61, Bibcode :2010LNCS.6060...45B, doi :10.1007/978-3-642-12476-1_3, ISBN 9783642124754.
^ ab Bentley, Jon L. ; Yao, Andrew C. (1976). "Un algoritmo casi óptimo para búsquedas ilimitadas". Information Processing Letters . 5 (3): 82–87. doi :10.1016/0020-0190(76)90071-5. ISSN 0020-0190.
^ de Jonsson, Håkan (19 de abril de 2011). «Búsqueda binaria exponencial». Archivado desde el original el 1 de junio de 2020. Consultado el 24 de marzo de 2014 .
^ Andersson, Arne; Thorup, Mikkel (2007). "Conjuntos ordenados dinámicos con árboles de búsqueda exponencial". Revista de la ACM . 54 (3): 13. arXiv : cs/0210006 . doi :10.1145/1236457.1236460. ISSN 0004-5411. S2CID 8175703.
^ Ukkonen, Esko (marzo de 1985). "Encontrar patrones aproximados en cadenas". Journal of Algorithms . 6 (1): 132–137. doi :10.1016/0196-6774(85)90023-9. ISSN 0196-6774.
^ Šošić, Martin; Šikić, Mile (23 de agosto de 2016). "Edlib: una biblioteca C/C++ para alineamiento de secuencias rápido y exacto usando la distancia de edición". doi :10.1101/070649. S2CID 3818517.