Sprong zoeken
Leuk vinden Binaire zoekopdracht Jump Search is een zoekalgoritme voor gesorteerde arrays. Het basisidee is om minder elementen (dan lineair zoeken ) door met vaste stappen vooruit te springen of enkele elementen over te slaan in plaats van alle elementen te doorzoeken.
Stel bijvoorbeeld dat we een array arr[] van grootte n hebben en een blok (waarover gesprongen moet worden) van grootte m. Vervolgens zoeken we in de indexen arr[0] arr[m] arr[2m].....arr[km] enzovoort. Zodra we het interval (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Laten we de volgende array bekijken: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). De lengte van de array is 16. De Jump-zoekopdracht zal de waarde 55 vinden met de volgende stappen, ervan uitgaande dat de te springen blokgrootte 4 is.
STAP 1: Spring van index 0 naar index 4;
STAP 2: Spring van index 4 naar index 8;
STAP 3: Spring van index 8 naar index 12;
STAP 4: Omdat het element op index 12 groter is dan 55, gaan we een stap terug om bij index 8 te komen.
STAP 5: Voer een lineaire zoekopdracht uit vanaf index 8 om element 55 te verkrijgen.
Prestaties in vergelijking met lineair en binair zoeken:
Als we het vergelijken met lineair en binair zoeken, komt het eruit: het is beter dan lineair zoeken, maar niet beter dan binair zoeken.
De oplopende volgorde van prestatie is:
lineair zoeken < jump search < binary search
Wat is de optimale blokgrootte die kan worden overgeslagen?
In het ergste geval moeten we n/m-sprongen maken en als de laatst gecontroleerde waarde groter is dan het element waarnaar moet worden gezocht, voeren we meer m-1-vergelijkingen uit voor lineair zoeken. Daarom zal het totale aantal vergelijkingen in het slechtste geval ((n/m) + m-1) zijn. De waarde van de functie ((n/m) + m-1) zal minimaal zijn als m = √n. Daarom is de beste stapgrootte m = √ N.
Algoritme stappen
- Jump Search is een algoritme voor het vinden van een specifieke waarde in een gesorteerde array door bepaalde stappen in de array te doorlopen.
- De stappen worden bepaald door de sqrt van de lengte van de array.
- Hier is een stapsgewijs algoritme voor de sprongzoekopdracht:
- Bepaal de stapgrootte m door de sqrt van de lengte van de array n te nemen.
- Begin bij het eerste element van de array en spring m stappen totdat de waarde op die positie groter is dan de doelwaarde.
Zodra een waarde groter dan het doel is gevonden, voert u een lineaire zoekopdracht uit, beginnend bij de vorige stap, totdat het doel is gevonden of totdat het duidelijk is dat het doel niet in de array staat.
Als het doel wordt gevonden, retourneert u de index. Als dit niet het geval is, retourneert u -1 om aan te geven dat het doel niet in de array is gevonden.
Voorbeeld 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 ; ?>
Uitgang:
Number 55 is at index 10
Tijdcomplexiteit: O(?n)
Hulpruimte: O(1)Voordelen van snel zoeken:
- Beter dan een lineaire zoektocht naar arrays waarbij de elementen uniform verdeeld zijn.
- Jump-zoeken heeft een lagere tijdscomplexiteit vergeleken met lineair zoeken naar grote arrays.
- Het aantal stappen dat bij sprongzoeken wordt genomen, is evenredig met de vierkantswortel van de grootte van de array, waardoor deze efficiënter wordt voor grote arrays.
- Het is gemakkelijker te implementeren in vergelijking met andere zoekalgoritmen zoals binair zoeken of ternair zoeken.
- Sprongzoeken werkt goed voor arrays waarbij de elementen op volgorde en uniform verdeeld zijn, omdat bij elke iteratie naar een nauwere positie in de array kan worden gesprongen.
Belangrijke punten:
- Werkt alleen met gesorteerde arrays.
- De optimale grootte van een te springen blok is (?n). Dit maakt de tijdcomplexiteit van Jump Search O(?n).
- De tijdscomplexiteit van Jump Search ligt tussen lineair zoeken ((O(n)) en binair zoeken (O(Log n)).
- Binair zoeken is beter dan Jump Search, maar Jump Search heeft het voordeel dat we slechts één keer teruggaan (Binary Search kan tot O(Log n) sprongen vereisen, rekening houdend met een situatie waarin het te doorzoeken element het kleinste element is of gewoon groter dan het kleinste). Dus in een systeem waar binair zoeken kostbaar is, gebruiken we Jump Search.
Referenties:
https://en.wikipedia.org/wiki/Jump_search
Als je GeeksforGeeks leuk vindt en een bijdrage wilt leveren, kun je ook een artikel schrijven met schrijf.geeksforgeeks.org of mail uw artikel naar [email protected]. Zie uw artikel verschijnen op de hoofdpagina van GeeksforGeeks en help andere Geeks. Schrijf opmerkingen als u iets onjuist vindt of als u meer informatie wilt delen over het hierboven besproken onderwerp.
