Jump Search
Mint Bináris keresés A Jump Search egy keresési algoritmus rendezett tömbökhöz. Az alapötlet az, hogy kevesebb elemet ellenőrizzünk (mint lineáris keresés ).
Tegyük fel például, hogy van egy n méretű arr[] tömbünk és m méretű (ugrandó) blokkunk. Ezután az indexekben keresünk arr[0] arr[m] arr[2m].....arr[km] és így tovább. Miután megtaláltuk az intervallumot (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Tekintsük a következő tömböt: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). A tömb hossza 16. Az ugráskeresés az 55 értéket fogja megtalálni a következő lépésekkel, feltételezve, hogy az ugrandó blokk mérete 4.
1. LÉPÉS: Ugrás a 0 indexről a 4 indexre;
2. LÉPÉS: Ugrás a 4-es indexről a 8-asra;
3. LÉPÉS: Ugrás a 8-as indexről a 12-esre;
4. LÉPÉS: Mivel a 12-es indexben lévő elem nagyobb, mint 55, egy lépést visszaugorunk, hogy elérjük a 8-as indexet.
5. LÉPÉS: Végezzen lineáris keresést a 8-as indexből, hogy megkapja az 55-ös elemet.
Teljesítmény a lineáris és bináris kereséshez képest:
Ha összehasonlítjuk a lineáris és a bináris kereséssel, akkor kijön, akkor jobb, mint a lineáris keresés, de nem jobb, mint a bináris keresés.
A teljesítmény növekvő sorrendje a következő:
lineáris keresés < jump search < binary search
Mekkora az optimális blokkméret, amelyet át kell hagyni?
Legrosszabb esetben n/m ugrást kell végeznünk, és ha az utoljára ellenőrzött érték nagyobb, mint a keresendő elem, akkor inkább m-1 összehasonlításokat végzünk lineáris kereséshez. Ezért az összehasonlítások teljes száma a legrosszabb esetben ((n/m) + m-1 lesz. A függvény értéke ((n/m) + m-1) akkor lesz minimális, ha m = √n. Ezért a legjobb lépésméret m = √ n.
Algoritmus lépései
- A Jump Search egy olyan algoritmus, amely egy adott értéket keres egy rendezett tömbben a tömb bizonyos lépései között ugrálva.
- A lépéseket a tömb hosszának sqrt-je határozza meg.
- Íme egy lépésenkénti algoritmus az ugráskereséshez:
- Határozzuk meg az m lépésméretet az n tömb hosszának sqrt értékével.
- Kezdje a tömb első elemével, és ugorjon m lépést, amíg az adott pozícióban lévő érték nagyobb lesz, mint a célérték.
Ha a célnál nagyobb értéket talált, hajtson végre lineáris keresést az előző lépéstől kezdve, amíg meg nem találja a célt, vagy egyértelművé válik, hogy a cél nincs a tömbben.
Ha a cél megtalálható, adja vissza az indexét. Ha nem, adja vissza a -1-et, jelezve, hogy a cél nem található a tömbben.
1. példa:
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 ; ?>
Kimenet:
Number 55 is at index 10
Időbonyolultság: O(?n)
Segédtér: O(1)A Jump Search előnyei:
- Jobb, mint egy olyan tömb lineáris keresése, ahol az elemek egyenletesen oszlanak el.
- Az ugrásos keresés időbeli bonyolultsága kisebb, mint a nagy tömbök lineáris keresése.
- Az ugráskeresésben megtett lépések száma arányos a tömb méretének négyzetgyökével, ami hatékonyabbá teszi a nagy tömbök esetében.
- Könnyebben megvalósítható más keresési algoritmusokhoz képest, mint például a bináris keresés vagy a hármas keresés.
- Az ugráskeresés jól működik azoknál a tömböknél, ahol az elemek sorrendben és egyenletes eloszlásban vannak, mivel minden iterációval közelebb tud ugrani a tömbben.
Fontos pontok:
- Csak rendezett tömbökkel működik.
- Az ugrandó blokk optimális mérete (? n). Ez teszi a Jump Search O(? n) időbeli összetettségét.
- A Jump Search időbeli összetettsége a lineáris keresés ((O(n)) és a bináris keresés (O(Log n)) között van.
- A bináris keresés jobb, mint az ugrásos keresés, de az ugrásos keresésnek megvan az az előnye, hogy csak egyszer lépünk vissza (a bináris keresés akár O(Log n) ugrást igényelhet, figyelembe véve azt a helyzetet, amikor a keresendő elem a legkisebb elem, vagy éppen nagyobb, mint a legkisebb). Tehát egy olyan rendszerben, ahol a bináris keresés költséges, a Jump Search-t használjuk.
Referenciák:
https://en.wikipedia.org/wiki/Jump_search
Ha szereted a GeeksforGeeks-t, és szeretnél hozzájárulni, akkor cikket is írhatsz a segítségével write.geeksforgeeks.org vagy küldje el cikkét a [email protected] címre. Tekintse meg cikkét a GeeksforGeeks főoldalán, és segítsen másoknak. Kérjük, írjon megjegyzéseket, ha bármi hibásat talál, vagy további információkat szeretne megosztani a fent tárgyalt témával kapcsolatban.
