Przeskocz wyszukiwanie
Tak jak Wyszukiwanie binarne Jump Search to algorytm wyszukiwania posortowanych tablic. Podstawową ideą jest sprawdzenie mniejszej liczby elementów (niż wyszukiwanie liniowe ) poprzez przeskakiwanie do przodu o ustalone kroki lub pomijanie niektórych elementów zamiast przeszukiwania wszystkich elementów.
Załóżmy na przykład, że mamy tablicę arr[] o rozmiarze n i blok (do przeskoczenia) o rozmiarze m. Następnie szukamy w indeksach arr[0] arr[m] arr[2m].....arr[km] i tak dalej. Gdy już znajdziemy odstęp (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Rozważmy następującą tablicę: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Długość tablicy wynosi 16. Wyszukiwanie skoku znajdzie wartość 55, wykonując następujące kroki, zakładając, że rozmiar bloku do przeskoczenia wynosi 4.
KROK 1: Skok z indeksu 0 do indeksu 4;
KROK 2: Skok z indeksu 4 do indeksu 8;
KROK 3: Skok z indeksu 8 do indeksu 12;
KROK 4: Ponieważ element o indeksie 12 jest większy niż 55, cofniemy się o krok i dotrzemy do indeksu 8.
KROK 5: Wykonaj wyszukiwanie liniowe od indeksu 8, aby uzyskać element 55.
Wydajność w porównaniu do wyszukiwania liniowego i binarnego:
Jeśli porównamy to z wyszukiwaniem liniowym i binarnym, wychodzi, że jest lepsze niż wyszukiwanie liniowe, ale nie lepsze niż wyszukiwanie binarne.
Rosnąca kolejność wykonań to:
wyszukiwanie liniowe < jump search < binary search
Jaki jest optymalny rozmiar bloku do pominięcia?
W najgorszym przypadku musimy wykonać skoki n/m i jeśli ostatnio sprawdzana wartość jest większa od szukanego elementu, przy szukaniu liniowym wykonujemy porównania m-1. Zatem całkowita liczba porównań w najgorszym przypadku będzie wynosić ((n/m) + m-1). Wartość funkcji ((n/m) + m-1) będzie minimalna, gdy m = √n. Dlatego najlepszy rozmiar kroku to m = √ N.
Kroki algorytmu
- Wyszukiwanie skokowe to algorytm znajdowania określonej wartości w posortowanej tablicy poprzez przeskakiwanie przez określone kroki w tablicy.
- Kroki są określone przez sqrt długości tablicy.
- Oto algorytm krok po kroku wyszukiwania skoku:
- Określ wielkość kroku m, biorąc sqrt długości tablicy n.
- Zacznij od pierwszego elementu tablicy i skacz o m kroków, aż wartość w tej pozycji będzie większa niż wartość docelowa.
Po znalezieniu wartości większej niż wartość docelowa należy przeprowadzić wyszukiwanie liniowe, zaczynając od poprzedniego kroku, aż do znalezienia wartości docelowej lub gdy będzie jasne, że wartości docelowej nie ma w tablicy.
Jeśli cel zostanie znaleziony, zwróć jego indeks. Jeśli nie, zwróć -1, aby wskazać, że celu nie odnaleziono w tablicy.
Przykład 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 ; ?>
Wyjście:
Number 55 is at index 10
Złożoność czasowa: O(?n)
Przestrzeń pomocnicza: O(1)Zalety wyszukiwania skokowego:
- Lepsze niż liniowe wyszukiwanie tablic, w których elementy są równomiernie rozłożone.
- Wyszukiwanie skokowe ma mniejszą złożoność czasową w porównaniu z wyszukiwaniem liniowym dużych tablic.
- Liczba kroków wykonywanych w wyszukiwaniu skokowym jest proporcjonalna do pierwiastka kwadratowego z rozmiaru tablicy, co czyni ją bardziej efektywną w przypadku dużych tablic.
- Jest łatwiejszy do wdrożenia w porównaniu z innymi algorytmami wyszukiwania, takimi jak wyszukiwanie binarne lub wyszukiwanie trójskładnikowe.
- Wyszukiwanie skokowe działa dobrze w przypadku tablic, w których elementy są uporządkowane i równomiernie rozmieszczone, ponieważ z każdą iteracją może przeskakiwać do bliżej pozycji w tablicy.
Ważne punkty:
- Działa tylko z posortowanymi tablicami.
- Optymalny rozmiar bloku do przeskoczenia to (? n). To sprawia, że złożoność czasowa wyszukiwania skokowego O(? n).
- Złożoność czasowa wyszukiwania skokowego mieści się pomiędzy wyszukiwaniem liniowym ((O(n)) a wyszukiwaniem binarnym (O(Log n)).
- Wyszukiwanie binarne jest lepsze niż wyszukiwanie skokowe, ale wyszukiwanie skokowe ma tę zaletę, że cofamy się tylko raz (wyszukiwanie binarne może wymagać skoków do O(log n), biorąc pod uwagę sytuację, w której przeszukiwany element jest najmniejszym elementem lub po prostu większym niż najmniejszy). Zatem w systemie, w którym wyszukiwanie binarne jest kosztowne, używamy wyszukiwania skokowego.
Referencje:
https://en.wikipedia.org/wiki/Jump_search
Jeśli podoba Ci się GeeksforGeeks i chcesz wnieść swój wkład, możesz także napisać artykuł za pomocą write.geeksforgeeks.org lub wyślij swój artykuł na adres [email protected]. Zobacz swój artykuł pojawiający się na stronie głównej GeeksforGeeks i pomóż innym Geekom. Napisz komentarz, jeśli znajdziesz coś nieprawidłowego lub chcesz udostępnić więcej informacji na temat omówiony powyżej.
