- Valor buscado
- Bloque actual
- Comparadas
- Descartadas
- Encontradas
Búsqueda por saltos
La búsqueda por saltos está a medio camino entre la búsqueda lineal y la binaria. Avanza por una lista ordenada en saltos de m posiciones, revisando solo el último valor de cada bloque, hasta llegar a un bloque cuyo último valor no es menor que el objetivo. Entonces recorre ese bloque desde el principio. Elige el valor y el tamaño del salto, y mira cuántas comparaciones necesitan los saltos y el recorrido. Pulsa Reproducir para ver la búsqueda, o Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto. La línea discontinua marca el valor que buscas, y la parte sombreada es el bloque actual. La búsqueda por saltos necesita una lista ordenada, así que una lista desordenada se ordena primero. Elige el valor, el tamaño del salto, cuántas barras hay, o escribe tus propios números. Con el tablero seleccionado, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.
Cómo funciona
- Elige el valor que buscar, el tamaño del salto y cuántas barras hay. O escribe tus propios números: la búsqueda por saltos los ordena primero.
- Pulsa Reproducir, o usa Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto de la búsqueda.
- Con 40 barras, prueba un tamaño de salto de 2 y de 8, y compara el número de comparaciones con el de √n.
Cómo funciona la búsqueda por saltos
Divide la lista ordenada en bloques de m valores. Mira el último valor del primer bloque. Si es menor que el objetivo, el objetivo no puede estar en ninguna parte de ese bloque, así que salta al final del bloque siguiente y vuelve a mirar. En cuanto el último valor de un bloque no sea menor, el objetivo solo puede estar en ese bloque: vuelve a su inicio y revisa sus valores uno a uno hasta encontrar el objetivo o pasarlo.
Elegir el tamaño del salto
Con n valores, los saltos cuestan hasta n/m comparaciones y el recorrido hasta m. Los saltos pequeños hacen corto el recorrido, pero numerosos los saltos; los grandes, lo contrario. El total n/m + m es mínimo cuando m = √n, lo que da unas 2√n comparaciones: como máximo 13 para 40 valores, frente a 40 de la búsqueda lineal y 6 de la binaria. La búsqueda por saltos nunca retrocede más de un bloque, lo que ayuda cuando moverse hacia atrás por los datos es lento.
Preguntas frecuentes
¿Cómo funciona la búsqueda por saltos?
En una lista ordenada, salta hacia delante de m en m posiciones y revisa el último valor de cada bloque. Cuando ese valor ya no es menor que el objetivo, el objetivo solo puede estar en ese bloque, que entonces recorre desde el principio.
¿Cuál es el mejor tamaño de salto?
√n, redondeado. Los saltos cuestan hasta n/m comparaciones y el recorrido hasta m, y su suma es mínima cuando ambos son iguales, con m = √n. Eso da unas 2√n comparaciones en el peor caso.
¿Es la búsqueda por saltos más rápida que la búsqueda binaria?
No, la búsqueda binaria necesita menos comparaciones: unas log₂ n frente a unas 2√n. Aun así, la búsqueda por saltos puede ganar cuando volver atrás por los datos es costoso, porque solo retrocede una vez, al inicio de un bloque.
¿Qué coincidencia encuentra cuando hay valores repetidos?
La primera. Cada bloque que salta termina con un valor menor que el objetivo, así que ningún bloque anterior puede contener una coincidencia, y el recorrido empieza al principio del bloque.
¿Se envían mis números a algún sitio?
No. La búsqueda se ejecuta en tu navegador, y tus últimos ajustes se quedan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor