Hop søgning
Ligesom Binær søgning Jump Search er en søgealgoritme for sorterede arrays. Den grundlæggende idé er at kontrollere færre elementer (end lineær søgning ) ved at hoppe fremad med faste trin eller springe nogle elementer over i stedet for at søge i alle elementer.
Antag for eksempel, at vi har en array arr[] af størrelse n og en blok (der skal springes) på størrelse m. Så søger vi i indekserne arr[0] arr[m] arr[2m].....arr[km] og så videre. Når vi finder intervallet (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Lad os overveje følgende array: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Længden af arrayet er 16. Jump-søgningen finder værdien 55 med følgende trin, forudsat at blokstørrelsen, der skal springes, er 4.
TRIN 1: Spring fra indeks 0 til indeks 4;
TRIN 2: Spring fra indeks 4 til indeks 8;
TRIN 3: Spring fra indeks 8 til indeks 12;
TRIN 4: Da elementet ved indeks 12 er større end 55, springer vi et trin tilbage for at komme til indeks 8.
TRIN 5: Udfør en lineær søgning fra indeks 8 for at få elementet 55.
Ydeevne sammenlignet med lineær og binær søgning:
Hvis vi sammenligner det med lineær og binær søgning, så kommer det ud, så er det bedre end lineær søgning, men ikke bedre end binær søgning.
Den stigende rækkefølge af ydeevne er:
lineær søgning < jump search < binary search
Hvad er den optimale blokstørrelse, der skal springes over?
I værste fald skal vi lave n/m hop, og hvis den sidst kontrollerede værdi er større end det element, der skal søges efter, udfører vi m-1 sammenligninger mere for lineær søgning. Derfor vil det samlede antal sammenligninger i værste fald være ((n/m) + m-1). Værdien af funktionen ((n/m) + m-1) vil være minimum, når m = √n. Derfor er den bedste trinstørrelse m = √ n.
Algoritme trin
- Jump Search er en algoritme til at finde en bestemt værdi i et sorteret array ved at springe gennem bestemte trin i arrayet.
- Trinnene bestemmes af sqrt af længden af arrayet.
- Her er en trin-for-trin algoritme til springsøgningen:
- Bestem trinstørrelsen m ved at tage sqrt af længden af arrayet n.
- Start ved det første element i arrayet og hop m trin, indtil værdien på den position er større end målværdien.
Når en værdi, der er større end målet, er fundet, udfør en lineær søgning startende fra det forrige trin, indtil målet er fundet, eller det er tydeligt, at målet ikke er i arrayet.
Hvis målet er fundet returner dets indeks. Hvis ikke returneres -1 for at angive, at målet ikke blev fundet i arrayet.
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 ; ?>
Produktion:
Number 55 is at index 10
Tidskompleksitet: O(?n)
Hjælpeplads: O(1)Fordele ved Jump Search:
- Bedre end en lineær søgning efter arrays, hvor elementerne er ensartet fordelt.
- Jump-søgning har en lavere tidskompleksitet sammenlignet med en lineær søgning efter store arrays.
- Antallet af trin, der tages i springsøgning, er proportionalt med kvadratroden af arrayets størrelse, hvilket gør det mere effektivt for store arrays.
- Det er nemmere at implementere sammenlignet med andre søgealgoritmer som binær søgning eller ternær søgning.
- Jump-søgning fungerer godt for arrays, hvor elementerne er i orden og ensartet fordelt, da den kan hoppe til en tættere position i arrayet med hver iteration.
Vigtige punkter:
- Fungerer kun med sorterede arrays.
- Den optimale størrelse af en blok, der skal springes, er (? n). Dette gør tidskompleksiteten af Jump Search O(? n).
- Tidskompleksiteten af Jump Search er mellem lineær søgning ((O(n)) og binær søgning (O(Log n)).
- Binær søgning er bedre end Jump Search, men Jump Search har den fordel, at vi kun går tilbage én gang (Binær søgning kan kræve op til O(Log n) hop overveje en situation, hvor det element, der skal søges i, er det mindste element eller bare større end det mindste). Så i et system, hvor binær søgning er dyr, bruger vi Jump Search.
Referencer:
https://en.wikipedia.org/wiki/Jump_search
Hvis du kan lide GeeksforGeeks og gerne vil bidrage, kan du også skrive en artikel ved hjælp af write.geeksforgeeks.org eller send din artikel til [email protected]. Se din artikel, der vises på GeeksforGeeks hovedside, og hjælp andre nørder. Skriv venligst kommentarer, hvis du finder noget forkert, eller hvis du vil dele flere oplysninger om emnet diskuteret ovenfor.
