Přejít vyhledávání
Jako Binární vyhledávání Jump Search je vyhledávací algoritmus pro seřazená pole. Základní myšlenkou je zkontrolovat méně prvků (než lineární vyhledávání ) skokem vpřed o pevné kroky nebo přeskakováním některých prvků namísto prohledávání všech prvků.
Předpokládejme například, že máme pole arr[] o velikosti n a blok (který má být přeskočen) o velikosti m. Poté hledáme v indexech arr[0] arr[m] arr[2m].....arr[km] a tak dále. Jakmile najdeme interval (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Uvažujme následující pole: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Délka pole je 16. Vyhledávání skokem najde hodnotu 55 s následujícími kroky za předpokladu, že velikost bloku, který má být přeskočen, je 4.
KROK 1: Skok z indexu 0 na index 4;
KROK 2: Skok z indexu 4 na index 8;
KROK 3: Skok z indexu 8 na index 12;
KROK 4: Protože prvek na indexu 12 je větší než 55, skočíme o krok zpět, abychom se dostali k indexu 8.
KROK 5: Proveďte lineární vyhledávání od indexu 8, abyste získali prvek 55.
Výkon ve srovnání s lineárním a binárním vyhledáváním:
Pokud to porovnáme s lineárním a binárním vyhledáváním, pak to vyjde lépe než lineární, ale ne lepší než binární.
Zvyšující se pořadí výkonu je:
lineární vyhledávání < jump search < binary search
Jaká je optimální velikost bloku, který má být přeskočen?
V nejhorším případě musíme provést n/m skoků a pokud je poslední kontrolovaná hodnota větší než hledaný prvek, provedeme m-1 porovnání spíše pro lineární vyhledávání. Celkový počet srovnání v nejhorším případě tedy bude ((n/m) + m-1). Hodnota funkce ((n/m) + m-1) bude minimální, když m = √n. Proto je nejlepší velikost kroku m = √ n.
Kroky algoritmu
- Jump Search je algoritmus pro nalezení konkrétní hodnoty v seřazeném poli skokem přes určité kroky v poli.
- Kroky jsou určeny sqrt délky pole.
- Zde je krok za krokem algoritmus pro vyhledávání skoků:
- Určete velikost kroku m tím, že vezmete sqrt délky pole n.
- Začněte na prvním prvku pole a přeskočte m kroků, dokud hodnota na této pozici nebude větší než cílová hodnota.
Jakmile je nalezena hodnota větší než cíl, proveďte lineární vyhledávání počínaje předchozím krokem, dokud není cíl nalezen nebo není jasné, že cíl není v poli.
Pokud je cíl nalezen, vraťte jeho index. Pokud ne, vraťte hodnotu -1, abyste označili, že cíl nebyl v poli nalezen.
Příklad 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 ; ?>
výstup:
Number 55 is at index 10
Časová složitost: O(?n)
Pomocný prostor: O(1)Výhody vyhledávání skoků:
- Lepší než lineární hledání polí, kde jsou prvky rovnoměrně rozmístěny.
- Vyhledávání skokem má nižší časovou náročnost ve srovnání s lineárním vyhledáváním velkých polí.
- Počet kroků provedených při vyhledávání skoků je úměrný druhé odmocnině velikosti pole, což je efektivnější pro velká pole.
- Je snazší implementovat ve srovnání s jinými vyhledávacími algoritmy, jako je binární vyhledávání nebo ternární vyhledávání.
- Vyhledávání skokem funguje dobře pro pole, kde jsou prvky v pořadí a rovnoměrně rozmístěné, protože může při každé iteraci přeskočit na bližší pozici v poli.
Důležité body:
- Funguje pouze s seřazenými poli.
- Optimální velikost bloku, který má být přeskočen, je (? n). To činí časovou složitost vyhledávání skokem O(? n).
- Časová složitost vyhledávání skoků je mezi lineárním vyhledáváním ((O(n)) a binárním vyhledáváním (O(Log n)).
- Binární vyhledávání je lepší než vyhledávání skokem, ale vyhledávání skokem má tu výhodu, že zpět procházíme pouze jednou (binární vyhledávání může vyžadovat až O(Log n) skoků, přičemž se uvažuje situace, kdy je prvek, který má být prohledán, nejmenší prvek nebo jen větší než nejmenší). Takže v systému, kde je binární vyhledávání nákladné, používáme Jump Search.
Reference:
https://cs.wikipedia.org/wiki/Jump_search
Pokud máte rádi GeeksforGeeks a chtěli byste přispět, můžete také napsat článek pomocí write.geeksforgeeks.org nebo pošlete svůj článek na [email protected]. Podívejte se na svůj článek na hlavní stránce GeeksforGeeks a pomozte ostatním Geeks. Napište prosím komentáře, pokud najdete něco nesprávného nebo se chcete podělit o více informací o výše uvedeném tématu.
