Búsqueda de salto

En informática , una búsqueda de salto o búsqueda de bloques se refiere a un algoritmo de búsqueda para listas ordenadas . Funciona comprobando primero todos los elementos L _km , donde${\displaystyle k\in \mathbb {N} }$y m es el tamaño del bloque, hasta que se encuentre un elemento que sea mayor que la clave de búsqueda . Para encontrar la posición exacta de la clave de búsqueda en la lista, se realiza una búsqueda lineal en la sublista L _{[( k -1) m , km ]} .

El valor óptimo de m es √ n , donde n es la longitud de la lista L . Dado que ambos pasos del algoritmo examinan, como máximo, √ n elementos, el algoritmo se ejecuta en tiempo O( √ n ). Esto es mejor que una búsqueda lineal , pero peor que una búsqueda binaria . La ventaja sobre esta última es que una búsqueda por saltos solo necesita retroceder una vez, mientras que una búsqueda binaria puede retroceder hasta log n veces. Esto puede ser importante si retroceder lleva mucho más tiempo que avanzar.

El algoritmo se puede modificar realizando múltiples niveles de búsqueda por salto en las sublistas, antes de realizar finalmente la búsqueda lineal . Para una búsqueda por salto de k niveles, el tamaño de bloque óptimo m _l para el ^nivel l (contando desde 1) es n ^(kl)/k . El algoritmo modificado realizará k saltos hacia atrás y se ejecutará en tiempo O( kn ^{1/( k +1)} ).

El algoritmo JumpSearch recibe como entrada: una lista ordenada L , su longitud n y una clave de búsqueda s . Su salida es: la posición de s en L , o nada si s no está en L.a ← 0 b ← ⌊√ n ⌋ mientras L min( b , n )-1 < s hacer a ← b b ← b + ⌊√ n ⌋ si a ≥ n entonces no devolver nadamientras L a < s hacer a ← a + 1 si a = min( b , n ) devolver nadaSi L a = s, entonces devuelve a; de lo contrario, no devuelve nada.

• Búsqueda de puntos de salto
• Lista de saltos
• Búsqueda por interpolación
• Búsqueda lineal : se ejecuta en tiempo O( n ), solo mira hacia adelante.
• Búsqueda binaria : se ejecuta en tiempo O(log n ), busca tanto hacia adelante como hacia atrás.

•  Este artículo incorpora material de dominio público de Paul E. Black. "búsqueda de salto" . Diccionario de algoritmos y estructuras de datos . NIST .
• Ben Shneiderman , Búsqueda por salto: una técnica de búsqueda secuencial rápida , CACM, 21(10):831-834, octubre de 1978.