Peršokti paieška
Patinka Dvejetainė paieška „Jump Search“ yra surūšiuotų masyvų paieškos algoritmas. Pagrindinė idėja yra patikrinti mažiau elementų (nei linijinė paieška ) šokinėjant į priekį fiksuotais žingsniais arba praleidžiant kai kuriuos elementus vietoje visų elementų paieškos.
Pavyzdžiui, tarkime, kad turime n dydžio masyvą arr[] ir m dydžio bloką (kurią reikia peršokti). Tada ieškome indeksuose arr[0] arr[m] arr[2m].....arr[km] ir pan. Kai rasime intervalą (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Let’s consider the following array: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Masyvo ilgis yra 16. Peršokimo paieška suras reikšmę 55, atlikdama šiuos veiksmus, darant prielaidą, kad peršokamo bloko dydis yra 4.
1 ŽINGSNIS: peršokti nuo indekso 0 į indeksą 4;
2 ŽINGSNIS: peršokti iš 4 indekso į 8;
3 ŽINGSNIS: peršokti nuo 8 indekso į 12;
4 ŽINGSNIS: Kadangi 12 indekso elementas yra didesnis nei 55, pereisime žingsnį atgal, kad pasiektume 8 indeksą.
5 ŽINGSNIS: atlikite linijinę paiešką iš 8 indekso, kad gautumėte elementą 55.
Našumas, palyginti su linijine ir dvejetaine paieška:
Jei palyginsime ją su linijine ir dvejetaine paieška, tada ji bus geriau nei tiesinė paieška, bet ne geriau nei dvejetainė paieška.
Didėjanti vykdymo tvarka yra tokia:
linijinė paieška < jump search < binary search
Koks yra optimalus bloko dydis, kurį reikia praleisti?
In the worst case we have to do n/m jumps and if the last checked value is greater than the element to be searched for we perform m-1 comparisons more for linear search. Todėl bendras palyginimų skaičius blogiausiu atveju bus ((n/m) + m-1). Funkcijos reikšmė ((n/m) + m-1) bus minimali, kai m = √n. Todėl geriausias žingsnio dydis yra m = √ n.
Algoritmo žingsniai
- Peršokimo paieška yra algoritmas, skirtas rasti konkrečią reikšmę surūšiuotame masyve, peršokant tam tikrus masyvo veiksmus.
- Žingsniai nustatomi pagal masyvo ilgio sqrt.
- Štai žingsnis po žingsnio šuolio paieškos algoritmas:
- Nustatykite žingsnio dydį m, paimdami masyvo n ilgio kvadratą.
- Pradėkite nuo pirmojo masyvo elemento ir peršokkite m žingsnių, kol reikšmė toje vietoje bus didesnė už tikslinę reikšmę.
Suradę reikšmę, didesnę už tikslą, atlikite linijinę paiešką, pradedant nuo ankstesnio veiksmo, kol bus rastas tikslas arba paaiškės, kad taikinio nėra masyve.
Jei tikslas rastas, grąžinkite jo indeksą. Jei ne, grąžinkite -1, nurodydami, kad taikinys masyve nerastas.
1 pavyzdys:
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 ; ?>
Išvestis:
Number 55 is at index 10
Laiko sudėtingumas: O(?n)
Pagalbinė erdvė: O(1)Peršokimo paieškos privalumai:
- Geriau nei tiesinė paieška masyvų, kuriuose elementai yra tolygiai paskirstyti.
- Peršokimo paieška turi mažesnį laiko sudėtingumą, palyginti su linijine didelių masyvų paieška.
- Žingsnių, atliktų atliekant šuolio paiešką, skaičius yra proporcingas masyvo dydžio kvadratinei šaknis, todėl jis yra efektyvesnis dideliems masyvams.
- Jį lengviau įgyvendinti, palyginti su kitais paieškos algoritmais, tokiais kaip dvejetainė paieška arba treji paieška.
- Peršokimo paieška gerai veikia masyvuose, kuriuose elementai yra tvarkingi ir tolygiai paskirstyti, nes kiekviena iteracija gali pereiti į artimesnę masyvo vietą.
Svarbūs punktai:
- Veikia tik su surūšiuotais masyvais.
- Optimalus peršokamo bloko dydis yra (? n). Dėl to peršokimo paieška tampa sudėtinga O(? n).
- Peršokimo paieškos sudėtingumas yra tarp linijinės paieškos ((O(n)) ir dvejetainės paieškos (O(Log n)).
- Dvejetainė paieška yra geresnė nei greitoji paieška, tačiau peršoka paieška turi pranašumą, kad grįžtame tik vieną kartą (dvejetainėje paieškoje gali prireikti iki O (Log n) šuolių, atsižvelgiant į situaciją, kai ieškomas elementas yra mažiausias elementas arba tiesiog didesnis už mažiausią). Taigi sistemoje, kurioje dvejetainė paieška yra brangi, naudojame „Jump Search“.
Nuorodos:
https://en.wikipedia.org/wiki/Jump_search
Jei jums patinka GeeksforGeeks ir norėtumėte prisidėti, taip pat galite parašyti straipsnį naudodami write.geeksforgeeks.org arba atsiųskite savo straipsnį adresu [email protected]. Peržiūrėkite savo straipsnį pagrindiniame GeeksforGeeks puslapyje ir padėkite kitiems Geeks. Rašykite komentarus, jei radote ką nors neteisingo arba norite pasidalinti daugiau informacijos apie aukščiau aptartą temą.
