Sprungsuche
Wie Binäre Suche Jump Search ist ein Suchalgorithmus für sortierte Arrays. Die Grundidee besteht darin, weniger Elemente zu überprüfen (als lineare Suche ), indem Sie in festen Schritten vorwärts springen oder einige Elemente überspringen, anstatt alle Elemente zu durchsuchen.
Angenommen, wir haben ein Array arr[] der Größe n und einen Block (der übersprungen werden soll) der Größe m. Dann suchen wir in den Indizes arr[0] arr[m] arr[2m].....arr[km] und so weiter. Sobald wir das Intervall gefunden haben (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Betrachten wir das folgende Array: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Die Länge des Arrays beträgt 16. Die Sprungsuche findet mit den folgenden Schritten den Wert 55 unter der Annahme, dass die zu überspringende Blockgröße 4 beträgt.
SCHRITT 1: Von Index 0 zu Index 4 springen;
SCHRITT 2: Von Index 4 zu Index 8 springen;
SCHRITT 3: Von Index 8 zu Index 12 springen;
SCHRITT 4: Da das Element bei Index 12 größer als 55 ist, springen wir einen Schritt zurück, um zu Index 8 zu gelangen.
SCHRITT 5: Führen Sie eine lineare Suche ab Index 8 durch, um das Element 55 zu erhalten.
Leistung im Vergleich zur linearen und binären Suche:
Wenn wir es mit der linearen und binären Suche vergleichen, kommt heraus, dass es besser als die lineare Suche, aber nicht besser als die binäre Suche ist.
Die aufsteigende Reihenfolge der Leistung ist:
lineare Suche < jump search < binary search
Was ist die optimale Blockgröße zum Überspringen?
Im schlimmsten Fall müssen wir n/m Sprünge machen und wenn der zuletzt überprüfte Wert größer ist als das zu suchende Element, führen wir für die lineare Suche mehr m-1 Vergleiche durch. Daher beträgt die Gesamtzahl der Vergleiche im schlimmsten Fall ((n/m) + m-1). Der Wert der Funktion ((n/m) + m-1) ist minimal, wenn m = √n. Daher ist die beste Schrittgröße m = √ N.
Algorithmusschritte
- Jump Search ist ein Algorithmus zum Suchen eines bestimmten Werts in einem sortierten Array durch Springen durch bestimmte Schritte im Array.
- Die Schritte werden durch das Quadrat der Länge des Arrays bestimmt.
- Hier ist ein Schritt-für-Schritt-Algorithmus für die Sprungsuche:
- Bestimmen Sie die Schrittgröße m, indem Sie das Quadrat der Länge des Arrays n nehmen.
- Beginnen Sie beim ersten Element des Arrays und springen Sie m Schritte, bis der Wert an dieser Position größer als der Zielwert ist.
Sobald ein Wert gefunden wird, der größer als das Ziel ist, führen Sie eine lineare Suche beginnend mit dem vorherigen Schritt durch, bis das Ziel gefunden wird oder klar ist, dass das Ziel nicht im Array enthalten ist.
Wenn das Ziel gefunden wird, wird dessen Index zurückgegeben. Wenn nicht, geben Sie -1 zurück, um anzuzeigen, dass das Ziel nicht im Array gefunden wurde.
Beispiel 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 ; ?>
Ausgabe:
Number 55 is at index 10
Zeitkomplexität: O(?n)
Hilfsraum: O(1)Vorteile der Sprungsuche:
- Besser als eine lineare Suche nach Arrays, bei denen die Elemente gleichmäßig verteilt sind.
- Die Sprungsuche weist im Vergleich zu einer linearen Suche für große Arrays eine geringere zeitliche Komplexität auf.
- Die Anzahl der Schritte, die bei der Sprungsuche ausgeführt werden, ist proportional zur Quadratwurzel der Größe des Arrays, was sie bei großen Arrays effizienter macht.
- Im Vergleich zu anderen Suchalgorithmen wie der binären Suche oder der ternären Suche ist es einfacher zu implementieren.
- Die Sprungsuche eignet sich gut für Arrays, in denen die Elemente geordnet und gleichmäßig verteilt sind, da sie bei jeder Iteration zu einer näheren Position im Array springen kann.
Wichtige Punkte:
- Funktioniert nur mit sortierten Arrays.
- Die optimale Größe eines zu überspringenden Blocks beträgt (? n). Dies macht die zeitliche Komplexität der Sprungsuche O(? n).
- Die zeitliche Komplexität der Sprungsuche liegt zwischen der linearen Suche ((O(n)) und der binären Suche (O(Log n)).
- Die binäre Suche ist besser als die Sprungsuche, hat aber den Vorteil, dass wir nur einmal zurückgehen (die binäre Suche kann bis zu O(Log n) Sprünge erfordern, wenn man bedenkt, dass das zu durchsuchende Element das kleinste Element oder nur größer als das kleinste ist). In einem System, in dem die binäre Suche kostspielig ist, verwenden wir die Sprungsuche.
Referenzen:
https://en.wikipedia.org/wiki/Jump_search
Wenn Ihnen GeeksforGeeks gefällt und Sie einen Beitrag leisten möchten, können Sie auch einen Artikel über schreiben write.geeksforgeeks.org oder senden Sie Ihren Artikel per E-Mail an [email protected]. Sehen Sie sich Ihren Artikel auf der Hauptseite von GeeksforGeeks an und helfen Sie anderen Geeks. Bitte schreiben Sie Kommentare, wenn Sie etwas Falsches finden oder weitere Informationen zu dem oben besprochenen Thema teilen möchten.
