En informática , una búsqueda exponencial (también llamado doble de búsqueda o al galope de búsqueda o de búsqueda Struzik ) [1] es un algoritmo , creado por Jon Bentley y Andrew Chi-Chih Yao en 1976, para la búsqueda de ordenadas, listas ilimitadas / infinitas. [2] Existen 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.
Clase | Algoritmo de búsqueda |
---|---|
Estructura de datos | Formación |
Rendimiento en el peor de los casos | O (log i ) |
Rendimiento en el mejor de los casos | O (1) |
Rendimiento medio | O (log i ) |
Complejidad espacial en el peor de los casos | O (1) |
La búsqueda exponencial también se puede utilizar para buscar en listas delimitadas. La búsqueda exponencial puede incluso superar las búsquedas más tradicionales de 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 el 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á en el tiempo 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 ordenada e ilimitada 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 residirí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, asumiendo 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 para la búsqueda binaria con la potencia anterior de 2, 2 j - 1 , siendo el límite inferior para la búsqueda binaria. [3]
// Devuelve la posición de la clave en la matriz arr de tamaño de longitud. plantilla < nombre de tipo T > int exponential_search ( T arr [], int tamaño , T clave ) { si ( tamaño == 0 ) { retorno NOT_FOUND ; } int límite = 1 ; while ( límite < tamaño && arr [ límite ] < clave ) { límite * = 2 ; } return binary_search ( arr , clave , límite / 2 , min ( límite + 1 , 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 se repite, 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 búsqueda clave, 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, la búsqueda binaria se realiza con el resultado de una falla, 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 de la búsqueda binaria, el ciclo while se ejecuta exactamenteveces. Dado que la lista está ordenada, después de duplicar el índice de búsquedaveces, el algoritmo estará en un índice de búsqueda mayor o igual que i como. Como tal, la primera etapa del algoritmo toma O (log i ) tiempo.
La segunda parte del algoritmo también toma O (log i ) tiempo. Como la segunda etapa es simplemente una búsqueda binaria, toma O (log n ) donde n es el tamaño del intervalo que se busca. El tamaño de este intervalo sería 2 j - 2 j - 1 donde, como se vio arriba, j = log i . Esto significa que el tamaño del intervalo que se busca 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 contraposición a 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, como antes, de modo que es más grande que la clave de búsqueda y es menor que la clave de búsqueda. Previamente,se determinó de manera unaria calculando la siguiente potencia de 2 (es decir, sumando 1 a j ). En la variación, se propone quese duplica en su lugar (por ejemplo, saltando de 2 2 a 2 4 en lugar de 2 3 ). El primero tal que es mayor que la clave de búsqueda forma un límite superior mucho más áspero que antes. Una vez esto se encuentra, el algoritmo pasa a su segunda etapa y se realiza una búsqueda binaria en el intervalo formado por y , dando el exponente del límite superior j más preciso . 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 ).
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, dando la variación de búsqueda binaria anidada en k . El tiempo de ejecución asintótico no cambia para las variaciones, ejecutándose en tiempo O (log i ), como con el algoritmo de búsqueda exponencial original.
Además, se puede proporcionar una estructura de datos con una versión ajustada de la propiedad de dedo dinámico cuando el resultado anterior de la búsqueda binaria anidada en k se usa en una matriz ordenada. [4] Con 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 que fue accedido y el elemento actual al que se accede.
Ver 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, 6060 , Springer, págs. 45–61, Bibcode : 2010LNCS.6060 ... 45B , doi : 10.1007 / 978-3-642-12476-1_3 , ISBN 9783642124754.
- ^ a b Bentley, Jon L .; Yao, Andrew C. (1976). "Un algoritmo casi óptimo para búsquedas ilimitadas". Cartas de procesamiento de información . 5 (3): 82–87. doi : 10.1016 / 0020-0190 (76) 90071-5 . ISSN 0020-0190 .
- ^ a b Jonsson, Håkan (19 de abril de 2011). "Búsqueda binaria exponencial" . Consultado el 24 de marzo de 2014 .
- ^ Andersson, Arne; Thorup, Mikkel (2007). "Conjuntos ordenados dinámicos con árboles de búsqueda exponenciales". Revista de la ACM . 54 (3): 13. arXiv : cs / 0210006 . doi : 10.1145 / 1236457.1236460 . ISSN 0004-5411 .