Salt de căutare
Ca Căutare binară Jump Search este un algoritm de căutare pentru tablouri sortate. Ideea de bază este să verificați mai puține elemente (decât căutare liniară ) sărind înainte cu pași fiși sau sărind unele elemente în loc de căutarea tuturor elementelor.
De exemplu, să presupunem că avem un tablou arr[] de dimensiunea n și un bloc (de sărit) de dimensiunea m. Apoi căutăm în indicii arr[0] arr[m] arr[2m].....arr[km] și așa mai departe. Odată ce găsim intervalul (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Să luăm în considerare următorul tablou: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Lungimea matricei este 16. Căutarea Jump va găsi valoarea 55 cu următorii pași presupunând că dimensiunea blocului care trebuie sărit este 4.
PASUL 1: Sari de la indicele 0 la indicele 4;
PASUL 2: Sari de la indexul 4 la indexul 8;
PASUL 3: Sari de la indicele 8 la indicele 12;
PASUL 4: Deoarece elementul de la indicele 12 este mai mare de 55, vom face un pas înapoi pentru a ajunge la indicele 8.
PASUL 5: Efectuați o căutare liniară din indexul 8 pentru a obține elementul 55.
Performanță în comparație cu căutarea liniară și binară:
Dacă o comparăm cu căutarea liniară și binară, atunci iese, atunci este mai bună decât căutarea liniară, dar nu mai bună decât căutarea binară.
Ordinea crescătoare a performanței este:
căutare liniară < jump search < binary search
Care este dimensiunea optimă a blocului care trebuie sărit?
In cel mai rau caz trebuie sa facem n/m salturi si daca ultima valoare verificata este mai mare decat elementul de cautat efectuam m-1 comparatii mai mult pentru cautare liniara. Prin urmare, numărul total de comparații în cel mai rău caz va fi ((n/m) + m-1). Valoarea funcției ((n/m) + m-1) va fi minimă când m = √n. Prin urmare, cea mai bună dimensiune a pasului este m = √ n.
Pași de algoritm
- Jump Search este un algoritm pentru găsirea unei anumite valori într-o matrice sortată, prin sărirea prin anumiți pași din matrice.
- Pașii sunt determinați de sqrt a lungimii tabloului.
- Iată un algoritm pas cu pas pentru căutarea prin salt:
- Determinați dimensiunea pasului m luând pătratul lungimii tabloului n.
- Începeți de la primul element al matricei și săriți m pași până când valoarea din acea poziție este mai mare decât valoarea țintă.
Odată ce este găsită o valoare mai mare decât ținta, efectuați o căutare liniară începând cu pasul anterior până când ținta este găsită sau este clar că ținta nu se află în matrice.
Dacă ținta este găsită returnați-i indexul. Dacă nu, returnați -1 pentru a indica că ținta nu a fost găsită în matrice.
Exemplul 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 ; ?>
Ieșire:
Number 55 is at index 10
Complexitatea timpului: O(?n)
Spațiu auxiliar: O(1)Avantajele Jump Search:
- Mai bine decât o căutare liniară a matricelor în care elementele sunt distribuite uniform.
- Căutarea prin salt are o complexitate de timp mai mică în comparație cu o căutare liniară pentru matrice mari.
- Numărul de pași făcuți în căutarea prin salt este proporțional cu rădăcina pătrată a dimensiunii matricei, ceea ce face mai eficient pentru matrice mari.
- Este mai ușor de implementat în comparație cu alți algoritmi de căutare, cum ar fi căutarea binară sau căutarea ternară.
- Căutarea prin salt funcționează bine pentru matrice în care elementele sunt în ordine și distribuite uniform, deoarece poate sări într-o poziție mai apropiată în matrice cu fiecare iterație.
Puncte importante:
- Funcționează numai cu matrice sortate.
- Dimensiunea optimă a unui bloc care trebuie sărit este (? n). Acest lucru face ca complexitatea temporală a Jump Search O(? n).
- Complexitatea temporală a Căutării cu salt este între Căutarea liniară ((O(n)) și Căutarea binară (O(Log n)).
- Căutarea binară este mai bună decât Jump Search, dar Jump Search are avantajul că ne parcurgem înapoi o singură dată (Binary Search poate necesita până la O(Log n) salturi, luând în considerare o situație în care elementul care trebuie căutat este cel mai mic element sau doar mai mare decât cel mai mic). Deci, într-un sistem în care căutarea binară este costisitoare, folosim Jump Search.
Referinte:
https://en.wikipedia.org/wiki/Jump_search
Dacă vă place GeeksforGeeks și doriți să contribui, puteți scrie și un articol folosind scrie.geeksforgeeks.org sau trimiteți articolul dumneavoastră la [email protected]. Vedeți articolul dvs. care apare pe pagina principală GeeksforGeeks și ajutați alți Geeks. Vă rugăm să scrieți comentarii dacă găsiți ceva incorect sau doriți să împărtășiți mai multe informații despre subiectul discutat mai sus.
