ジャンプ検索
のように 二分探索 Jump Search は、ソートされた配列の検索アルゴリズムです。基本的な考え方は、より少ない要素をチェックすることです。 線形探索 ) すべての要素を検索する代わりに、固定ステップで先に進むか、一部の要素をスキップします。
たとえば、サイズ n の配列 arr[] とサイズ m の (ジャンプされる) ブロックがあるとします。次に、インデックス arr[0] arr[m] arr[2m]....arr[km] などを検索します。間隔 (arr[km]) を見つけたら、 < x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element x.
次の配列を考えてみましょう: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610)。配列の長さは 16 です。ジャンプするブロック サイズが 4 であると仮定すると、ジャンプ検索では次の手順で値 55 が見つかります。
ステップ 1: インデックス 0 からインデックス 4 にジャンプします。
ステップ 2: インデックス 4 からインデックス 8 にジャンプします。
ステップ 3: インデックス 8 からインデックス 12 にジャンプします。
ステップ 4: インデックス 12 の要素は 55 より大きいため、1 ステップ戻ってインデックス 8 に戻ります。
ステップ 5: インデックス 8 から線形検索を実行して、要素 55 を取得します。
線形探索および二分探索と比較したパフォーマンス:
線形探索と二分探索と比較すると、線形探索よりは優れていますが、二分探索よりは優れていません。
パフォーマンスの昇順は次のとおりです。
線形探索 < jump search < binary search
スキップされる最適なブロック サイズはどれくらいですか?
最悪の場合、n/m 回のジャンプを実行する必要があり、最後にチェックした値が検索対象の要素より大きい場合は、線形検索のためにさらに m-1 回の比較を実行します。したがって、最悪の場合の比較の合計数は ((n/m) + m-1) になります。関数 ((n/m) + m-1) の値は、m = √n のときに最小になります。したがって、最適なステップ サイズは m = √ です。 n.
アルゴリズムのステップ
- ジャンプ検索は、配列内の特定のステップをジャンプして、ソートされた配列内の特定の値を見つけるアルゴリズムです。
- ステップは配列の長さの 2 乗によって決まります。
- ジャンプ検索の段階的なアルゴリズムは次のとおりです。
- 配列 n の長さの 2 乗を取得して、ステップ サイズ m を決定します。
- 配列の最初の要素から開始し、その位置の値がターゲット値より大きくなるまで m ステップジャンプします。
ターゲットより大きい値が見つかったら、ターゲットが見つかるまで、またはターゲットが配列内にないことが明らかになるまで、前のステップから線形検索を実行します。
ターゲットが見つかった場合は、そのインデックスを返します。そうでない場合は、ターゲットが配列内に見つからなかったことを示す -1 を返します。
例 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 ; ?>
出力：
Number 55 is at index 10
時間計算量 : O(?n)
補助スペース : O(1)ジャンプ検索の利点:
- 要素が均一に分布している配列の線形検索よりも優れています。
- ジャンプ検索は、大規模な配列の線形検索に比べて時間の複雑さが低くなります。
- ジャンプ検索で実行されるステップ数は配列のサイズの平方根に比例するため、大きな配列の場合はより効率的になります。
- 二分検索や三分検索などの他の検索アルゴリズムと比較して実装が簡単です。
- ジャンプ検索は、反復ごとに配列内のより近い位置にジャンプできるため、要素が順序どおりに配置され、均一に分散されている配列に適しています。
重要な点:
- ソートされた配列でのみ機能します。
- ジャンプされるブロックの最適なサイズは (? n) です。これにより、ジャンプ検索の時間計算量は O(? n) になります。
- ジャンプ検索の時間計算量は、線形検索 ((O(n)) と二分検索 (O(Log n)) の間です。
- 二分検索はジャンプ検索より優れていますが、ジャンプ検索には 1 回だけ遡ることができるという利点があります (二分検索では、検索対象の要素が最小要素であるか、最小要素よりもわずかに大きいという状況を考慮して、最大 O(Log n) 個のジャンプが必要となる場合があります)。したがって、二分探索にコストがかかるシステムでは、ジャンプ探索を使用します。
参考文献:
https://en.wikipedia.org/wiki/Jump_search
GeeksforGeeks が好きで貢献したい場合は、次を使用して記事を書くこともできます。 write.geeksforgeeks.org または、記事を [email protected] にメールで送信してください。 GeeksforGeeks のメイン ページにあなたの記事が掲載されているのを見て、他のギークを助けてください。間違っている点を見つけた場合、または上記のトピックについてさらに詳しい情報を共有したい場合は、コメントを書いてください。
