Complejidad Temporal
Mejor: O(1)
Prom: O(√n)
Peor: O(√n)
Jump Search funciona en arreglos ordenados saltando hacia adelante en pasos fijos y luego realizando una búsqueda lineal dentro del bloque identificado.
Cómo funciona:
1. Calcular el tamaño óptimo de salto: √n
2. Saltar a través del arreglo en bloques hasta encontrar uno donde podría estar el objetivo
3. Realizar una búsqueda lineal dentro de ese bloque
4. Retornar el índice si se encuentra, -1 en caso contrario
Complejidad Temporal:
Mejor: O(1)
Promedio: O(√n)
Peor: O(√n)
Complejidad Espacial: O(1)
Propiedades:
- Requiere arreglo ordenado
- Mejor que búsqueda lineal, más simple que búsqueda binaria
- Tamaño de salto óptimo: √n
Jump Search es útil cuando retroceder es costoso (por ejemplo, en listas enlazadas) comparado con Binary Search que requiere acceso aleatorio.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Jump Search (Búsqueda por Saltos)?
- Jump Search funciona en arreglos ordenados saltando hacia adelante en pasos fijos y luego realizando una búsqueda lineal dentro del bloque identificado.
- ¿Cuál es la complejidad de Jump Search (Búsqueda por Saltos)?
- Tiempo (promedio): O(√n) · Espacio: O(1)
- ¿Para quién es este visualizador de Jump Search (Búsqueda por Saltos)?
- La visualización de Jump Search (Búsqueda por Saltos) está pensada para nivel intermedio, dentro de la categoría Búsqueda. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Jump Search (Búsqueda por Saltos)?
- En la misma categoría (Búsqueda) puedes explorar: Binary Search, Linear Search, Interpolation Search. Todos tienen visualización interactiva.