Skoči Traži
Kao Binarno pretraživanje Jump Search je algoritam pretraživanja za sortirane nizove. Osnovna ideja je provjeriti manje elemenata (od linearno pretraživanje ) skakanjem unaprijed fiksnim koracima ili preskakanjem nekih elemenata umjesto pretraživanja svih elemenata.
Na primjer, pretpostavimo da imamo polje arr[] veličine n i blok (koji treba preskočiti) veličine m. Zatim tražimo u indeksima arr[0] arr[m] arr[2m].....arr[km] i tako dalje. Nakon što pronađemo interval (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Razmotrimo sljedeći niz: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Duljina niza je 16. Pretraživanje skokova će pronaći vrijednost 55 sa sljedećim koracima uz pretpostavku da je veličina bloka koji treba preskočiti 4.
KORAK 1: Skok s indeksa 0 na indeks 4;
KORAK 2: Skok s indeksa 4 na indeks 8;
KORAK 3: Skok s indeksa 8 na indeks 12;
KORAK 4: Budući da je element na indeksu 12 veći od 55, skočit ćemo korak unatrag da dođemo do indeksa 8.
KORAK 5: Izvedite linearno pretraživanje od indeksa 8 da biste dobili element 55.
Izvedba u usporedbi s linearnim i binarnim pretraživanjem:
Ako ga usporedimo s linearnim i binarnim pretraživanjem, ispada da je bolji od linearnog pretraživanja, ali ne bolji od binarnog pretraživanja.
Rastući redoslijed izvedbe je:
linearno pretraživanje < jump search < binary search
Koja je optimalna veličina bloka za preskakanje?
U najgorem slučaju moramo napraviti n/m skokova i ako je zadnja provjerena vrijednost veća od elementa koji se traži, izvodimo m-1 usporedbe više za linearno pretraživanje. Stoga će ukupni broj usporedbi u najgorem slučaju biti ((n/m) + m-1). Vrijednost funkcije ((n/m) + m-1) bit će minimalna kada je m = √n. Stoga je najbolja veličina koraka m = √ n.
Koraci algoritma
- Jump Search algoritam je za pronalaženje određene vrijednosti u sortiranom nizu skakanjem kroz određene korake u nizu.
- Koraci su određeni sqrtom duljine niza.
- Ovdje je algoritam korak po korak za pretraživanje skokova:
- Odredite veličinu koraka m uzimajući sqrt duljine niza n.
- Započnite od prvog elementa niza i skačite m koraka dok vrijednost na tom mjestu ne bude veća od ciljne vrijednosti.
Nakon što se pronađe vrijednost veća od cilja, izvedite linearno pretraživanje počevši od prethodnog koraka dok se cilj ne pronađe ili dok ne postane jasno da cilj nije u nizu.
Ako je cilj pronađen, vrati njegov indeks. Ako ne vrati -1 da označi da cilj nije pronađen u nizu.
Primjer 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 ; ?>
Izlaz:
Number 55 is at index 10
Vremenska složenost: O(?n)
Pomoćni prostor: O(1)Prednosti Jump Searcha:
- Bolje od linearne pretrage za nizove u kojima su elementi ravnomjerno raspoređeni.
- Preskočno pretraživanje ima nižu vremensku složenost u usporedbi s linearnim pretraživanjem velikih nizova.
- Broj koraka u pretraživanju skokova proporcionalan je kvadratnom korijenu veličine niza što ga čini učinkovitijim za velike nizove.
- Lakše ga je implementirati u usporedbi s drugim algoritmima pretraživanja poput binarnog pretraživanja ili ternarnog pretraživanja.
- Pretraživanje skokom dobro funkcionira za nizove u kojima su elementi u redu i ravnomjerno raspoređeni jer može skočiti na bližu poziciju u nizu sa svakom iteracijom.
Važne točke:
- Radi samo sa sortiranim nizovima.
- Optimalna veličina bloka koji se skače je (? n). Ovo čini vremensku složenost Skočnog pretraživanja O(? n).
- Vremenska složenost Skočnog pretraživanja je između linearnog pretraživanja ((O(n)) i binarnog pretraživanja (O(Log n)).
- Binarno pretraživanje je bolje od preskočnog pretraživanja, ali preskočno pretraživanje ima prednost u tome što se samo jednom vraćamo natrag (binarno pretraživanje može zahtijevati do O(Log n) skokova uzimajući u obzir situaciju u kojoj je element koji se traži najmanji element ili samo veći od najmanjeg). Dakle, u sustavu gdje je binarno pretraživanje skupo, koristimo preskočno pretraživanje.
Reference:
https://en.wikipedia.org/wiki/Jump_search
Ako vam se sviđa GeeksforGeeks i želite doprinijeti, možete napisati članak koristeći write.geeksforgeeks.org ili pošaljite svoj članak na [email protected]. Pogledajte kako se vaš članak pojavljuje na glavnoj stranici GeeksforGeeksa i pomozite drugim Geekovima. Molimo napišite komentare ako pronađete bilo što netočno ili želite podijeliti više informacija o temi o kojoj se gore raspravljalo.
