Ako Binárne vyhľadávanie Jump Search je vyhľadávací algoritmus pre triedené polia. Základnou myšlienkou je skontrolovať menej prvkov (ako lineárne vyhľadávanie ) skokom dopredu o pevné kroky alebo preskočením niektorých prvkov namiesto prehľadávania všetkých prvkov.
Predpokladajme napríklad, že máme pole arr[] veľkosti n a blok (na preskočenie) veľkosti m. Potom hľadáme v indexoch arr[0] arr[m] arr[2m].....arr[km] atď. Keď nájdeme 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 o nasledujúcom poli: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Dĺžka poľa je 16. Vyhľadávanie skokom nájde hodnotu 55 s nasledujúcimi krokmi za predpokladu, že veľkosť bloku, ktorý sa má preskočiť, 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: Keďže prvok na indexe 12 je väčší ako 55, skočíme o krok späť, aby sme sa dostali k indexu 8.
KROK 5: Vykonajte lineárne vyhľadávanie od indexu 8, aby ste získali prvok 55.
Výkon v porovnaní s lineárnym a binárnym vyhľadávaním:
Ak to porovnáme s lineárnym a binárnym vyhľadávaním, potom to vyjde lepšie ako lineárne vyhľadávanie, ale nie lepšie ako binárne vyhľadávanie.
Zvyšujúce sa poradie výkonu je:
lineárne vyhľadávanie < jump search < binary search
Aká je optimálna veľkosť bloku na preskočenie?
V najhoršom prípade musíme urobiť n/m skokov a ak je posledná kontrolovaná hodnota väčšia ako hľadaný prvok, vykonáme m-1 porovnaní skôr pre lineárne vyhľadávanie. Preto celkový počet porovnaní v najhoršom prípade bude ((n/m) + m-1). Hodnota funkcie ((n/m) + m-1) bude minimálna, keď m = √n. Preto je najlepšia veľkosť kroku m = √ n.
Kroky algoritmu
- Jump Search je algoritmus na nájdenie konkrétnej hodnoty v zoradenom poli skokom cez určité kroky v poli.
- Kroky sú určené sqrt dĺžky poľa.
- Tu je krok za krokom algoritmus na vyhľadávanie skokov:
- Určte veľkosť kroku m pomocou sqrt dĺžky poľa n.
- Začnite od prvého prvku poľa a preskočte m krokov, kým hodnota na tejto pozícii nebude väčšia ako cieľová hodnota.
Keď sa nájde hodnota väčšia ako cieľ, vykonajte lineárne vyhľadávanie počnúc predchádzajúcim krokom, kým sa nenájde cieľ alebo kým nie je jasné, že cieľ nie je v poli.
Ak je cieľ nájdený, vráťte jeho index. Ak nie, vráťte hodnotu -1 na označenie, že cieľ sa v poli nenašiel.
Príklad 1:
C++// C++ program to implement Jump Search #include
#include
// 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); } }
# 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# 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); } }
<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 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á zložitosť: O(?n)
Pomocný priestor: O(1)
Výhody Jump Search:
- Lepšie ako lineárne vyhľadávanie polí, kde sú prvky rovnomerne rozložené.
- Skokové vyhľadávanie má nižšiu časovú zložitosť v porovnaní s lineárnym vyhľadávaním veľkých polí.
- Počet krokov vykonaných pri skokovom vyhľadávaní je úmerný druhej odmocnine veľkosti poľa, vďaka čomu je efektívnejší pre veľké polia.
- Je jednoduchšia na implementáciu v porovnaní s inými vyhľadávacími algoritmami, ako je binárne vyhľadávanie alebo ternárne vyhľadávanie.
- Skokové vyhľadávanie funguje dobre pre polia, kde sú prvky v poradí a rovnomerne rozložené, pretože pri každej iterácii môže preskočiť na bližšiu pozíciu v poli.
Dôležité body:
- Funguje iba so zoradenými poľami.
- Optimálna veľkosť bloku, ktorý sa má preskočiť, je (? n). To robí časovú zložitosť vyhľadávania skokom O(? n).
- Časová zložitosť vyhľadávania skokov je medzi lineárnym vyhľadávaním ((O(n)) a binárnym vyhľadávaním (O(Log n)).
- Binárne vyhľadávanie je lepšie ako vyhľadávanie skokom, ale vyhľadávanie skokom má tú výhodu, že prechádzame späť iba raz (Binárne vyhľadávanie môže vyžadovať až O (Log n) skokov, pričom sa uvažuje o situácii, keď je prvok, ktorý sa má hľadať, najmenší prvok alebo len väčší ako najmenší). Takže v systéme, kde je binárne vyhľadávanie nákladné, používame vyhľadávanie skokov.
Referencie:
https://en.wikipedia.org/wiki/Jump_search
Ak máte radi GeeksforGeeks a chceli by ste prispieť, môžete tiež napísať článok pomocou write.geeksforgeeks.org alebo pošlite svoj článok na [email protected]. Pozrite si, ako sa váš článok zobrazuje na hlavnej stránke GeeksforGeeks, a pomôžte tak ostatným Geeks. Ak nájdete niečo nesprávne, alebo ak sa chcete podeliť o viac informácií o téme diskutovanej vyššie, napíšte komentáre.