Búsqueda por saltos
La búsqueda por saltos es como buscas una página en un libro sin índice: avanzas un buen trozo cada vez, mirando los números de página, y cuando te has pasado, hojeas hacia atrás el último trozo. En una lista ordenada necesita muchas menos comparaciones que revisar cada valor.
La idea
En una lista ordenada, el último valor de un bloque te dice si el objetivo puede siquiera estar en ese bloque: si es menor que el objetivo, todos los valores del bloque también lo son. Así que no hace falta mirar dentro. Revisa por turno el último valor de cada bloque, saltando bloques enteros, hasta que uno no sea menor que el objetivo. Entonces el objetivo solo puede estar en ese bloque: recórrelo desde su inicio.
Un ejemplo
Busquemos 23 en 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, con bloques de 3. El primer bloque termina en 8, que es menor, así que se salta. El segundo termina en 23, que no es menor, así que 23 solo puede estar en 12, 16, 23. Al recorrerlo salen 12, 16 y luego 23: encontrado tras 5 comparaciones, donde la búsqueda lineal necesita 6 y la binaria 3. Si se busca 40, los finales de bloque 8, 23 y 72 llevan al bloque 38, 56, 72; 38 es menor y 56 ya es mayor, así que 40 no está: otra vez 5 comparaciones.
Por qué √n
Con bloques de m valores, encontrar el bloque correcto cuesta como máximo unas n/m comparaciones y recorrerlo como máximo m. Pocos saltos largos alargan el recorrido; muchos saltos cortos alargan los saltos. La suma n/m + m es mínima cuando ambas partes son iguales, con m = √n, donde vale unas 2√n. Para 40 valores, eso son bloques de 6 y como máximo 13 comparaciones; para un millón de valores, bloques de 1000 y unas 2000 comparaciones.
Dónde encaja
La búsqueda binaria necesita menos comparaciones, unas log₂ n. Pero salta de un lado a otro por toda la lista, mientras que la búsqueda por saltos solo avanza y retrocede una vez, al inicio de un bloque. Eso la hacía atractiva para datos en cinta o en una estructura enlazada, donde volver atrás es lento. Ben Shneiderman la describió como «jump searching» en 1978. La misma idea de dividir en bloques de √n, a menudo llamada descomposición en raíz cuadrada, aparece en muchos otros algoritmos.
Pruébala
Abre la app, elige un valor en Buscar y pulsa Paso. Cada salto resalta el último valor de un bloque; los bloques saltados se atenúan, y el bloque que puede contener el objetivo se sombrea mientras se recorre. Con 40 barras, cambia Tamaño del salto de √n a 2 u 8 y mira cómo cambia el equilibrio entre saltos y recorrido.
Preguntas frecuentes
¿Cuál es la complejidad temporal de la búsqueda por saltos?
O(√n) con bloques de √n valores: como máximo unas 2√n comparaciones. Necesita O(1) de memoria adicional y una lista ordenada.
¿Qué diferencia hay entre la búsqueda por saltos y la búsqueda binaria?
La búsqueda binaria reduce a la mitad la parte restante cada vez y necesita unas log₂ n comparaciones, pero va y viene. La búsqueda por saltos avanza a pasos fijos y recorre un bloque, necesita unas 2√n comparaciones y solo retrocede una vez.
¿Se puede usar la búsqueda binaria en el último bloque?
Sí. Buscar en el bloque con búsqueda binaria reduce el recorrido de m comparaciones a unas log₂ m. Los saltos siguen costando n/m, así que entonces compensan bloques más grandes.
¿Necesita la búsqueda por saltos una lista ordenada?
Sí. Saltar un bloque solo es seguro porque, si su último valor es menor, todos sus valores lo son. La app ordena primero una lista desordenada.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba la búsqueda por saltos