Salta la ricerca
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.
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 using namespace std ; int jumpSearch ( int arr [] int x int n ) { // Finding block size to be jumped int step = sqrt ( n ); // Finding the block where element is // present (if it is present) int 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 int main () { int arr [] = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); // Find the index of 'x' using Jump Search int index = jumpSearch ( arr x n ); // Print the index where 'x' is located cout < < ' n Number ' < < x < < ' is at index ' < < index ; return 0 ; } // Contributed by nuclode
C #include #include int min ( int a int b ){ if ( b > a ) return a ; else return b ; } int jumpsearch ( int arr [] int x int n ) { // Finding block size to be jumped int step = sqrt ( n ); // Finding the block where element is // present (if it is present) int 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 ; } int main () { int arr [] = { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 }; int x = 55 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); int index = jumpsearch ( arr x n ); if ( index >= 0 ) printf ( 'Number is at %d index' index ); else printf ( 'Number is not exist in the array' ); return 0 ; } // This code is contributed by Susobhan Akhuli
Java // 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 ); } }
Python # 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# // 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 ); } }
JavaScript < 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 // 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.
