Como Búsqueda binaria Jump Search es un algoritmo de búsqueda para matrices ordenadas. La idea básica es comprobar menos elementos (que búsqueda lineal ) saltando hacia adelante mediante pasos fijos u omitiendo algunos elementos en lugar de buscar todos los elementos.
Por ejemplo, supongamos que tenemos una matriz arr[] de tamaño n y un bloque (a saltar) de tamaño m. Luego buscamos en los índices arr[0] arr[m] arr[2m].....arr[km] y así sucesivamente. Una vez que encontramos el intervalo (arr[km]< x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Consideremos la siguiente matriz: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). La longitud de la matriz es 16. La búsqueda de salto encontrará el valor de 55 con los siguientes pasos asumiendo que el tamaño del bloque a saltar es 4.
PASO 1: Saltar del índice 0 al índice 4;
PASO 2: Salte del índice 4 al índice 8;
PASO 3: Salte del índice 8 al índice 12;
PASO 4: Dado que el elemento en el índice 12 es mayor que 55, retrocederemos un paso para llegar al índice 8.
PASO 5: Realice una búsqueda lineal desde el índice 8 para obtener el elemento 55.
Rendimiento en comparación con la búsqueda lineal y binaria:
Si lo comparamos con la búsqueda lineal y binaria, resulta que es mejor que la búsqueda lineal, pero no mejor que la búsqueda binaria.
El orden creciente de ejecución es:
búsqueda lineal < jump search < binary search
¿Cuál es el tamaño de bloque óptimo que se debe omitir?
En el peor de los casos tenemos que hacer n/m saltos y si el último valor comprobado es mayor que el elemento a buscar realizamos comparaciones m-1 más para búsqueda lineal. Por tanto, el número total de comparaciones en el peor de los casos será ((n/m) + m-1). El valor de la función ((n/m) + m-1) será mínimo cuando m = √n. Por lo tanto, el mejor tamaño de paso es m = √ norte.
Pasos del algoritmo
- Jump Search es un algoritmo para encontrar un valor específico en una matriz ordenada saltando ciertos pasos en la matriz.
- Los pasos están determinados por la raíz cuadrada de la longitud de la matriz.
- Aquí hay un algoritmo paso a paso para la búsqueda de salto:
- Determine el tamaño del paso m tomando la raíz cuadrada de la longitud de la matriz n.
- Comience en el primer elemento de la matriz y salte m pasos hasta que el valor en esa posición sea mayor que el valor objetivo.
Una vez que se encuentra un valor mayor que el objetivo, realice una búsqueda lineal comenzando desde el paso anterior hasta que se encuentre el objetivo o quede claro que el objetivo no está en la matriz.
Si se encuentra el objetivo, devuelva su índice. De lo contrario, devuelve -1 para indicar que el objetivo no se encontró en la matriz.
Ejemplo 1:
C++// C++ program to implement Jump Search #include
#include
// Java program to implement Jump Search. public class JumpSearch { public static int jumpSearch(int[] arr int x) { int n = arr.length; // Finding block size to be jumped int step = (int)Math.floor(Math.sqrt(n)); // Finding the block where element is // present (if it is present) int prev = 0; for (int minStep = Math.min(step n)-1; arr[minStep] < x; minStep = Math.min(step n)-1) { prev = step; step += (int)Math.floor(Math.sqrt(n)); if (prev >= n) return -1; } // Doing a linear search for x in block // beginning with prev. while (arr[prev] < x) { prev++; // If we reached next block or end of // array element is not present. if (prev == Math.min(step n)) return -1; } // If element is found if (arr[prev] == x) return prev; return -1; } // Driver program to test function public static void main(String [ ] args) { int arr[] = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610}; int x = 55; // Find the index of 'x' using Jump Search int index = jumpSearch(arr x); // Print the index where 'x' is located System.out.println('nNumber ' + x + ' is at index ' + index); } }
# Python3 code to implement Jump Search import math def jumpSearch( arr x n ): # Finding block size to be jumped step = math.sqrt(n) # Finding the block where element is # present (if it is present) prev = 0 while arr[int(min(step n)-1)] < x: prev = step step += math.sqrt(n) if prev >= n: return -1 # Doing a linear search for x in # block beginning with prev. while arr[int(prev)] < x: prev += 1 # If we reached next block or end # of array element is not present. if prev == min(step n): return -1 # If element is found if arr[int(prev)] == x: return prev return -1 # Driver code to test function arr = [ 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ] x = 55 n = len(arr) # Find the index of 'x' using Jump Search index = jumpSearch(arr x n) # Print the index where 'x' is located print('Number' x 'is at index' '%.0f'%index) # This code is contributed by 'Sharad_Bhardwaj'.
// C# program to implement Jump Search. using System; public class JumpSearch { public static int jumpSearch(int[] arr int x) { int n = arr.Length; // Finding block size to be jumped int step = (int)Math.Sqrt(n); // Finding the block where the element is // present (if it is present) int prev = 0; for (int minStep = Math.Min(step n)-1; arr[minStep] < x; minStep = Math.Min(step n)-1) { prev = step; step += (int)Math.Sqrt(n); if (prev >= n) return -1; } // Doing a linear search for x in block // beginning with prev. while (arr[prev] < x) { prev++; // If we reached next block or end of // array element is not present. if (prev == Math.Min(step n)) return -1; } // If element is found if (arr[prev] == x) return prev; return -1; } // Driver program to test function public static void Main() { int[] arr = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610}; int x = 55; // Find the index of 'x' using Jump Search int index = jumpSearch(arr x); // Print the index where 'x' is located Console.Write('Number ' + x + ' is at index ' + index); } }
<script> // Javascript program to implement Jump Search function jumpSearch(arr x n) { // Finding block size to be jumped let step = Math.sqrt(n); // Finding the block where element is // present (if it is present) let prev = 0; for (int minStep = Math.Min(step n)-1; arr[minStep] < x; minStep = Math.Min(step n)-1) { prev = step; step += Math.sqrt(n); if (prev >= n) return -1; } // Doing a linear search for x in block // beginning with prev. while (arr[prev] < x) { prev++; // If we reached next block or end of // array element is not present. if (prev == Math.min(step n)) return -1; } // If element is found if (arr[prev] == x) return prev; return -1; } // Driver program to test function let arr = [0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610]; let x = 55; let n = arr.length; // Find the index of 'x' using Jump Search let index = jumpSearch(arr x n); // Print the index where 'x' is located document.write(`Number ${x} is at index ${index}`); // This code is contributed by _saurabh_jaiswal </script>
// PHP program to implement Jump Search function jumpSearch($arr $x $n) { // Finding block size to be jumped $step = sqrt($n); // Finding the block where element is // present (if it is present) $prev = 0; while ($arr[min($step $n)-1] < $x) { $prev = $step; $step += sqrt($n); if ($prev >= $n) return -1; } // Doing a linear search for x in block // beginning with prev. while ($arr[$prev] < $x) { $prev++; // If we reached next block or end of // array element is not present. if ($prev == min($step $n)) return -1; } // If element is found if ($arr[$prev] == $x) return $prev; return -1; } // Driver program to test function $arr = array( 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ); $x = 55; $n = sizeof($arr) / sizeof($arr[0]); // Find the index of '$x' using Jump Search $index = jumpSearch($arr $x $n); // Print the index where '$x' is located echo 'Number '.$x.' is at index ' .$index; return 0; ?> Producción:
Number 55 is at index 10
Complejidad del tiempo: O (? n)
Espacio auxiliar: O(1)
Ventajas de la búsqueda de salto:
- Mejor que una búsqueda lineal de matrices donde los elementos están distribuidos uniformemente.
- La búsqueda por salto tiene una complejidad temporal menor en comparación con una búsqueda lineal para matrices grandes.
- El número de pasos dados en la búsqueda de salto es proporcional a la raíz cuadrada del tamaño de la matriz, lo que la hace más eficiente para matrices grandes.
- Es más fácil de implementar en comparación con otros algoritmos de búsqueda como la búsqueda binaria o la búsqueda ternaria.
- La búsqueda con salto funciona bien para matrices donde los elementos están en orden y distribuidos uniformemente, ya que puede saltar a una posición más cercana en la matriz con cada iteración.
Puntos importantes:
- Funciona sólo con matrices ordenadas.
- El tamaño óptimo de un bloque a saltar es (? n). Esto hace que la complejidad temporal de Jump Search sea O (? n).
- La complejidad temporal de Jump Search está entre la búsqueda lineal ((O(n)) y la búsqueda binaria (O(Log n)).
- La búsqueda binaria es mejor que la búsqueda con salto, pero la búsqueda con salto tiene la ventaja de que retrocedemos solo una vez (la búsqueda binaria puede requerir hasta O (Log n) saltos; considere una situación en la que el elemento a buscar es el elemento más pequeño o simplemente más grande que el más pequeño). Entonces, en un sistema donde la búsqueda binaria es costosa, utilizamos Jump Search.
Referencias:
https://en.wikipedia.org/wiki/Jump_search
Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando escribir.geeksforgeeks.org o envíe su artículo por correo a [email protected]. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema discutido anteriormente.