Hoppa Sök
Som Binär sökning Jump Search är en sökalgoritm för sorterade arrayer. Grundidén är att kontrollera färre element (än linjär sökning ) genom att hoppa framåt med fasta steg eller hoppa över vissa element i stället för att söka efter alla element.
Anta till exempel att vi har en array arr[] av storleken n och ett block (som ska hoppa) av storleken m. Sedan söker vi i indexen arr[0] arr[m] arr[2m].....arr[km] och så vidare. När vi väl hittar intervallet (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Låt oss överväga följande array: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Längden på arrayen är 16. Hoppsökningen hittar värdet 55 med följande steg förutsatt att blockstorleken som ska hoppa är 4.
STEG 1: Hoppa från index 0 till index 4;
STEG 2: Hoppa från index 4 till index 8;
STEG 3: Hoppa från index 8 till index 12;
STEG 4: Eftersom elementet vid index 12 är större än 55 hoppar vi tillbaka ett steg för att komma till index 8.
STEG 5: Utför en linjär sökning från index 8 för att få elementet 55.
Prestanda i jämförelse med linjär och binär sökning:
Om vi jämför det med linjär och binär sökning så kommer den ut så är det bättre än linjär sökning men inte bättre än binär sökning.
Den ökande ordningen för prestanda är:
linjär sökning < jump search < binary search
Vilken är den optimala blockstorleken att hoppa över?
I värsta fall måste vi göra n/m hopp och om det senast kontrollerade värdet är större än elementet som ska sökas efter utför vi m-1 jämförelser mer för linjär sökning. Därför blir det totala antalet jämförelser i värsta fall ((n/m) + m-1). Värdet på funktionen ((n/m) + m-1) kommer att vara minimum när m = √n. Därför är den bästa stegstorleken m = √ n.
Algoritmsteg
- Jump Search är en algoritm för att hitta ett specifikt värde i en sorterad array genom att hoppa genom vissa steg i arrayen.
- Stegen bestäms av sqrt av längden på arrayen.
- Här är en steg-för-steg-algoritm för hoppsökningen:
- Bestäm stegstorleken m genom att ta sqrt av längden på arrayen n.
- Börja vid det första elementet i arrayen och hoppa m steg tills värdet på den positionen är större än målvärdet.
När ett värde som är större än målet hittats utför en linjär sökning med början från föregående steg tills målet hittas eller det är tydligt att målet inte finns i arrayen.
Om målet hittas returnera dess index. Om inte, returnera -1 för att indikera att målet inte hittades i arrayen.
Exempel 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
Tidskomplexitet: O(?n)
Hjälputrymme: O(1)Fördelar med Jump Search:
- Bättre än en linjär sökning efter arrayer där elementen är jämnt fördelade.
- Hoppsökning har en lägre tidskomplexitet jämfört med en linjär sökning efter stora arrayer.
- Antalet steg som tas i hoppsökning är proportionell mot kvadratroten av storleken på arrayen, vilket gör den mer effektiv för stora arrayer.
- Det är lättare att implementera jämfört med andra sökalgoritmer som binär sökning eller ternär sökning.
- Hoppsökning fungerar bra för arrayer där elementen är i ordning och jämnt fördelade eftersom den kan hoppa till en närmare position i arrayen med varje iteration.
Viktiga punkter:
- Fungerar endast med sorterade arrayer.
- Den optimala storleken på ett block som ska hoppas är (? n). Detta gör tidskomplexiteten för Jump Search O(? n).
- Tidskomplexiteten för Jump Search är mellan linjär sökning ((O(n)) och binär sökning (O(Log n)).
- Binär sökning är bättre än Jump Search men Jump Search har fördelen att vi bara går bakåt en gång (Binär sökning kan kräva upp till O(Log n) hopp överväg en situation där elementet som ska sökas är det minsta elementet eller bara större än det minsta). Så i ett system där binär sökning är kostsam använder vi Jump Search.
Referenser:
https://en.wikipedia.org/wiki/Jump_search
Om du gillar GeeksforGeeks och vill bidra kan du också skriva en artikel med hjälp av write.geeksforgeeks.org eller maila din artikel till [email protected]. Se din artikel som visas på GeeksforGeeks huvudsida och hjälp andra nördar. Skriv kommentarer om du hittar något felaktigt eller om du vill dela mer information om ämnet som diskuterats ovan.
