Come Ricerca binaria Jump Search è un algoritmo di ricerca per array ordinati. L'idea di base è controllare meno elementi (di ricerca lineare ) saltando avanti per passaggi fissi o saltando alcuni elementi invece di cercare tutti gli elementi.
Ad esempio supponiamo di avere un array arr[] di dimensione n e un blocco (da saltare) di dimensione m. Poi cerchiamo negli indici arr[0] arr[m] arr[2m].....arr[km] e così via. Una volta trovato l'intervallo (arr[km]< x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Consideriamo il seguente array: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). La lunghezza dell'array è 16. La ricerca Jump troverà il valore 55 con i passaggi successivi assumendo che la dimensione del blocco da saltare sia 4.
PASSO 1: Salta dall'indice 0 all'indice 4;
PASSO 2: Salta dall'indice 4 all'indice 8;
PASSO 3: Salta dall'indice 8 all'indice 12;
PASSO 4: Poiché l'elemento all'indice 12 è maggiore di 55, faremo un passo indietro per arrivare all'indice 8.
PASSO 5: eseguire una ricerca lineare dall'indice 8 per ottenere l'elemento 55.
Prestazioni rispetto alla ricerca lineare e binaria:
Se la confrontiamo con la ricerca lineare e binaria, risulta che è migliore della ricerca lineare ma non migliore della ricerca binaria.
sostituire tutto Java
L'ordine crescente di esecuzione è:
ricerca lineare < jump search < binary search
Qual è la dimensione ottimale del blocco da saltare?
Nel caso peggiore dobbiamo fare n/m salti e se l'ultimo valore controllato è maggiore dell'elemento da cercare eseguiamo m-1 confronti in più per la ricerca lineare. Pertanto il numero totale di confronti nel caso peggiore sarà ((n/m) + m-1). Il valore della funzione ((n/m) + m-1) sarà minimo quando m = √n. Pertanto la migliore dimensione del passo è m = √ N.
Passaggi dell'algoritmo
- Jump Search è un algoritmo per trovare un valore specifico in un array ordinato saltando attraverso determinati passaggi nell'array.
- I passaggi sono determinati dal quadrato della lunghezza dell'array.
- Ecco un algoritmo passo passo per la ricerca del salto:
- Determina la dimensione del passo m prendendo il quadrato della lunghezza dell'array n.
- Inizia dal primo elemento dell'array e salta m passi finché il valore in quella posizione è maggiore del valore di destinazione.
Una volta trovato un valore maggiore del target, eseguire una ricerca lineare a partire dal passaggio precedente finché non viene trovato il target o finché non è chiaro che il target non è nell'array.
Se l'obiettivo viene trovato, restituisci il suo indice. In caso contrario, restituisce -1 per indicare che la destinazione non è stata trovata nell'array.
Esempio 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; ?> Produzione:
Number 55 is at index 10
Complessità temporale: O(?n)
Spazio ausiliario: O(1)
Vantaggi della ricerca rapida:
- Meglio di una ricerca lineare di array in cui gli elementi sono distribuiti uniformemente.
- La ricerca per salto ha una complessità temporale inferiore rispetto a una ricerca lineare per array di grandi dimensioni.
- Il numero di passaggi eseguiti nella ricerca per salto è proporzionale alla radice quadrata della dimensione dell'array, rendendola più efficiente per gli array di grandi dimensioni.
- È più semplice da implementare rispetto ad altri algoritmi di ricerca come la ricerca binaria o la ricerca ternaria.
- La ricerca per salto funziona bene per gli array in cui gli elementi sono in ordine e distribuiti uniformemente poiché può passare a una posizione più vicina nell'array con ogni iterazione.
Punti importanti:
- Funziona solo con array ordinati.
- La dimensione ottimale di un blocco da saltare è (? n). Ciò rende la complessità temporale della ricerca per salto O(? n).
- La complessità temporale della ricerca per salto è compresa tra la ricerca lineare ((O(n)) e la ricerca binaria (O(Log n)).
- La ricerca binaria è migliore della ricerca per salto ma la ricerca per salto ha il vantaggio di tornare indietro solo una volta (la ricerca binaria può richiedere fino a O (Log n) salti, considerare una situazione in cui l'elemento da cercare è l'elemento più piccolo o semplicemente più grande del più piccolo). Quindi, in un sistema in cui la ricerca binaria è costosa, utilizziamo Jump Search.
Riferimenti:
https://en.wikipedia.org/wiki/Jump_search
Se ti piace GeeksforGeeks e desideri contribuire puoi anche scrivere un articolo utilizzando write.geeksforgeeks.org oppure invia il tuo articolo via email a [email protected]. Guarda il tuo articolo apparire sulla pagina principale di GeeksforGeeks e aiuta altri Geeks. Scrivi commenti se trovi qualcosa di sbagliato o se desideri condividere maggiori informazioni sull'argomento discusso sopra.