Atla Arama
Beğenmek İkili Arama Jump Search, sıralanmış diziler için bir arama algoritmasıdır. Temel fikir daha az öğeyi kontrol etmektir (daha fazla) doğrusal arama ) sabit adımlarla ileriye atlayarak veya tüm öğeleri aramak yerine bazı öğeleri atlayarak.
Örneğin, n boyutunda bir arr[] dizimiz ve m boyutunda (atlanacak) bir bloğumuz olduğunu varsayalım. Daha sonra arr[0] arr[m] arr[2m]....arr[km] vb. dizinlerinde arama yaparız. Aralığı bulduktan sonra (arr[km] < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
Şu diziyi ele alalım: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610). Dizinin uzunluğu 16'dır. Atlama araması, atlanacak blok boyutunun 4 olduğunu varsayarak aşağıdaki adımlarla 55 değerini bulacaktır.
ADIM 1: Dizin 0'dan dizin 4'e atlayın;
ADIM 2: Dizin 4'ten dizin 8'e atlayın;
ADIM 3: Dizin 8'den dizin 12'ye atlayın;
ADIM 4: İndeks 12'deki eleman 55'ten büyük olduğundan, indeks 8'e gelmek için bir adım geriye atlayacağız.
ADIM 5: 55. elemanı elde etmek için 8. indeksten doğrusal bir arama yapın.
Doğrusal ve ikili aramaya kıyasla performans:
Eğer bunu doğrusal ve ikili aramayla karşılaştırırsak, o zaman doğrusal aramadan daha iyi olduğu ancak ikili aramadan daha iyi olmadığı ortaya çıkar.
Performansın artan sırası şöyledir:
doğrusal arama < jump search < binary search
Atlanacak en uygun blok boyutu nedir?
En kötü durumda n/m atlamalar yapmak zorunda kalırız ve son kontrol edilen değer aranacak elemandan büyükse doğrusal arama için m-1 karşılaştırmalarını daha fazla yaparız. Bu nedenle en kötü durumda toplam karşılaştırma sayısı ((n/m) + m-1) olacaktır. ((n/m) + m-1) fonksiyonunun değeri m = √n olduğunda minimum olacaktır. Bu nedenle en iyi adım boyutu m = √ N.
Algoritma adımları
- Atlamalı Arama, dizideki belirli adımları atlayarak sıralanmış bir dizideki belirli bir değeri bulmaya yönelik bir algoritmadır.
- Adımlar dizinin uzunluğunun karesine göre belirlenir.
- Atlamalı arama için adım adım bir algoritma aşağıda verilmiştir:
- n dizisinin uzunluğunun karesini alarak m adım boyutunu belirleyin.
- Dizinin ilk elemanından başlayın ve o konumdaki değer hedef değerden büyük olana kadar m adım atlayın.
Hedeften daha büyük bir değer bulunduğunda, önceki adımdan başlayarak hedef bulunana veya hedefin dizide olmadığı anlaşılana kadar doğrusal bir arama yapın.
Hedef bulunursa indeksini döndürün. Değilse, hedefin dizide bulunmadığını belirtmek için -1 değerini döndürün.
Örnek 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 ; ?>
Çıkış:
Number 55 is at index 10
Zaman Karmaşıklığı : O(?n)
Yardımcı Alan : O(1)Jump Search'ün Avantajları:
- Öğelerin eşit şekilde dağıtıldığı diziler için doğrusal aramadan daha iyidir.
- Atlamalı arama, büyük diziler için doğrusal aramaya kıyasla daha düşük bir zaman karmaşıklığına sahiptir.
- Atlamalı aramada atılan adım sayısı, dizi boyutunun kareköküyle orantılı olduğundan büyük diziler için daha verimli olur.
- İkili arama veya üçlü arama gibi diğer arama algoritmalarıyla karşılaştırıldığında uygulanması daha kolaydır.
- Atlamalı arama, her yinelemede dizide daha yakın bir konuma atlayabildiğinden, öğelerin sıralı ve eşit şekilde dağıtıldığı diziler için iyi çalışır.
Önemli noktalar:
- Yalnızca sıralanmış dizilerle çalışır.
- Atlanacak bloğun optimal boyutu (?n)'dir. Bu, Atlamalı Arama O(?n)'nin zaman karmaşıklığını artırır.
- Jump Search'ün zaman karmaşıklığı Doğrusal Arama ((O(n)) ile İkili Arama (O(Log n)) arasındadır.
- İkili Arama, Atlamalı Arama'dan daha iyidir ancak Atlamalı Arama, yalnızca bir kez geriye gitme avantajına sahiptir (Aranan öğenin en küçük öğe olduğu veya en küçükten biraz daha büyük olduğu bir durumu göz önünde bulundurarak İkili Arama, O(Log n) kadar atlama gerektirebilir). Yani ikili aramanın maliyetli olduğu bir sistemde Jump Search'ü kullanıyoruz.
Referanslar:
https://en.wikipedia.org/wiki/Jump_search
GeeksforGeeks'i beğendiyseniz ve katkıda bulunmak istiyorsanız, kullanarak bir makale de yazabilirsiniz. write.geeksforgeeks.org veya makalenizi [email protected] adresine gönderin. Makalenizin GeeksforGeeks ana sayfasında görünmesini sağlayın ve diğer Geek'lere yardımcı olun. Yanlış bir şey bulursanız veya yukarıda tartışılan konu hakkında daha fazla bilgi paylaşmak istiyorsanız lütfen yorumlarınızı yazın.
