Hoppsøk
Like Binært søk Jump Search er en søkealgoritme for sorterte matriser. Den grunnleggende ideen er å sjekke færre elementer (enn lineært søk ) ved å hoppe foran med faste trinn eller hoppe over noen elementer i stedet for å søke i alle elementene.
Anta for eksempel at vi har en array arr[] av størrelse n og en blokk (som skal hoppes) av størrelse m. Så søker vi i indeksene arr[0] arr[m] arr[2m].....arr[km] og så videre. Når vi finner intervallet (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
La oss vurdere følgende matrise: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Lengden på matrisen er 16. Hoppsøket vil finne verdien 55 med følgende trinn forutsatt at blokkstørrelsen som skal hoppes er 4.
TRINN 1: Hopp fra indeks 0 til indeks 4;
TRINN 2: Hopp fra indeks 4 til indeks 8;
TRINN 3: Hopp fra indeks 8 til indeks 12;
TRINN 4: Siden elementet ved indeks 12 er større enn 55, vil vi hoppe tilbake et trinn for å komme til indeks 8.
TRINN 5: Utfør et lineært søk fra indeks 8 for å få element 55.
Ytelse sammenlignet med lineært og binært søk:
Hvis vi sammenligner det med lineært og binært søk så kommer det ut, så er det bedre enn lineært søk, men ikke bedre enn binært søk.
Den økende ytelsesrekkefølgen er:
lineært søk < jump search < binary search
Hva er den optimale blokkstørrelsen som skal hoppes over?
I verste fall må vi gjøre n/m hopp og hvis den sist sjekkede verdien er større enn elementet som skal søkes etter, utfører vi m-1 sammenligninger mer for lineært søk. Derfor vil det totale antallet sammenligninger i verste fall være ((n/m) + m-1). Verdien av funksjonen ((n/m) + m-1) vil være minimum når m = √n. Derfor er den beste trinnstørrelsen m = √ n.
Algoritmetrinn
- Jump Search er en algoritme for å finne en spesifikk verdi i en sortert matrise ved å hoppe gjennom bestemte trinn i matrisen.
- Trinnene bestemmes av sqrt av lengden på matrisen.
- Her er en steg-for-steg-algoritme for hoppsøket:
- Bestem trinnstørrelsen m ved å ta sqrt av lengden på matrisen n.
- Start ved det første elementet i matrisen og hopp m trinn til verdien ved den posisjonen er større enn målverdien.
Når en verdi større enn målet er funnet, utfør et lineært søk fra forrige trinn til målet er funnet, eller det er tydelig at målet ikke er i matrisen.
Hvis målet blir funnet, returner dets indeks. Hvis ikke, returner -1 for å indikere at målet ikke ble funnet i matrisen.
Eksempel 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 ; ?>
Produksjon:
Number 55 is at index 10
Tidskompleksitet: O(?n)
Hjelpeområde: O(1)Fordeler med Jump Search:
- Bedre enn et lineært søk etter matriser der elementene er jevnt fordelt.
- Hoppsøk har lavere tidskompleksitet sammenlignet med et lineært søk etter store matriser.
- Antall skritt i hoppsøk er proporsjonalt med kvadratroten av størrelsen på matrisen, noe som gjør den mer effektiv for store matriser.
- Det er enklere å implementere sammenlignet med andre søkealgoritmer som binært søk eller ternært søk.
- Hoppsøk fungerer bra for matriser der elementene er i orden og jevnt fordelt, da det kan hoppe til en nærmere posisjon i matrisen med hver iterasjon.
Viktige punkter:
- Fungerer bare med sorterte arrays.
- Den optimale størrelsen på en blokk som skal hoppes er (? n). Dette gjør tidskompleksiteten til Jump Search O(? n).
- Tidskompleksiteten til Jump Search er mellom lineært søk ((O(n)) og binært søk (O(Log n)).
- Binært søk er bedre enn Jump Search, men Jump Search har fordelen at vi går tilbake kun én gang (Binært søk kan kreve opptil O(Log n) hopp vurdere en situasjon der elementet som skal søkes er det minste elementet eller bare større enn det minste). Så i et system der binært søk er kostbart bruker vi Jump Search.
Referanser:
https://en.wikipedia.org/wiki/Jump_search
Hvis du liker GeeksforGeeks og ønsker å bidra, kan du også skrive en artikkel ved å bruke write.geeksforgeeks.org eller send artikkelen til [email protected]. Se artikkelen din som vises på GeeksforGeeks hovedside og hjelp andre Geeks. Skriv kommentarer hvis du finner noe feil eller du vil dele mer informasjon om emnet diskutert ovenfor.
