Skoči iskanje
Všeč mi je Binarno iskanje Jump Search je iskalni algoritem za razvrščene nize. Osnovna ideja je preveriti manj elementov (kot linearno iskanje ) s skokom naprej po določenih korakih ali preskokom nekaterih elementov namesto iskanja po vseh elementih.
Na primer, predpostavimo, da imamo matriko arr[] velikosti n in blok (ki ga je treba preskočiti) velikosti m. Nato iščemo v indeksih arr[0] arr[m] arr[2m].....arr[km] in tako naprej. Ko najdemo interval (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Oglejmo si naslednjo matriko: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Dolžina matrike je 16. Iskanje po skoku bo našlo vrednost 55 z naslednjimi koraki ob predpostavki, da je velikost bloka, ki ga želite preskočiti, 4.
KORAK 1: Skok z indeksa 0 na indeks 4;
KORAK 2: Skok z indeksa 4 na indeks 8;
3. KORAK: Skok z indeksa 8 na indeks 12;
KORAK 4: Ker je element pri indeksu 12 večji od 55, bomo skočili korak nazaj, da pridemo do indeksa 8.
5. KORAK: Izvedite linearno iskanje od indeksa 8, da dobite element 55.
Zmogljivost v primerjavi z linearnim in binarnim iskanjem:
Če ga primerjamo z linearnim in binarnim iskanjem, se izkaže, da je boljše od linearnega iskanja, vendar ne boljše od binarnega iskanja.
Naraščajoči vrstni red uspešnosti je:
linearno iskanje < jump search < binary search
Kakšna je optimalna velikost bloka, ki ga je treba preskočiti?
V najslabšem primeru moramo narediti n/m skokov in če je zadnja preverjena vrednost večja od elementa, ki ga je treba iskati, izvedemo več primerjav m-1 za linearno iskanje. Zato bo skupno število primerjav v najslabšem primeru ((n/m) + m-1). Vrednost funkcije ((n/m) + m-1) bo najmanjša, ko je m = √n. Zato je najboljša velikost koraka m = √ n.
Koraki algoritma
- Preskočno iskanje je algoritem za iskanje določene vrednosti v razvrščeni matriki s skakanjem skozi določene korake v matriki.
- Koraki so določeni s sqrt dolžine polja.
- Tu je algoritem korak za korakom za iskanje skokov:
- Določite velikost koraka m tako, da vzamete sqrt dolžine niza n.
- Začnite pri prvem elementu matrike in preskakujte m korakov, dokler vrednost na tem mestu ni večja od ciljne vrednosti.
Ko je najdena vrednost, večja od cilja, izvedite linearno iskanje, začenši s prejšnjim korakom, dokler ni cilj najden ali pa je jasno, da cilja ni v matriki.
Če je cilj najden, vrni njegov indeks. Če ne vrne -1, ki nakazuje, da cilj ni bil najden v matriki.
Primer 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 ; ?>
Izhod:
Number 55 is at index 10
Časovna zahtevnost: O(?n)
Pomožni prostor: O(1)Prednosti Jump Search:
- Bolje kot linearno iskanje nizov, kjer so elementi enakomerno porazdeljeni.
- Preskočno iskanje ima nižjo časovno zahtevnost v primerjavi z linearnim iskanjem velikih nizov.
- Število korakov, opravljenih pri iskanju po skokih, je sorazmerno s kvadratnim korenom velikosti niza, zaradi česar je učinkovitejše pri velikih nizih.
- Lažje ga je implementirati v primerjavi z drugimi algoritmi iskanja, kot sta binarno ali ternarno iskanje.
- Preskočno iskanje dobro deluje pri nizih, kjer so elementi urejeni in enakomerno porazdeljeni, saj lahko z vsako ponovitvijo skoči na bližji položaj v nizu.
Pomembne točke:
- Deluje samo z razvrščenimi nizi.
- Optimalna velikost bloka, ki ga je treba preskočiti, je (? n). Zaradi tega je skokovito iskanje časovno zapleteno O(? n).
- Časovna kompleksnost skočnega iskanja je med linearnim iskanjem ((O(n)) in binarnim iskanjem (O(Log n)).
- Binarno iskanje je boljše od skočnega iskanja, vendar ima skočno iskanje to prednost, da se vrnemo le enkrat (binarno iskanje lahko zahteva do O(Log n) skokov, upoštevajte situacijo, ko je element, ki ga želite iskati, najmanjši element ali samo večji od najmanjšega). Torej v sistemu, kjer je binarno iskanje drago, uporabljamo skokovito iskanje.
Reference:
https://en.wikipedia.org/wiki/Jump_search
Če vam je GeeksforGeeks všeč in bi radi prispevali, lahko tudi napišete članek z uporabo write.geeksforgeeks.org ali pošljite svoj članek na naslov [email protected]. Oglejte si, da se vaš članek pojavi na glavni strani GeeksforGeeks in pomagajte drugim Geekom. Prosimo, napišite komentarje, če najdete karkoli napačnega ali želite deliti več informacij o zgoraj obravnavani temi.
