コンピュータサイエンスにおいて、ジャンプ検索またはブロック検索は、順序付きリストの検索アルゴリズムを指します。このアルゴリズムは、まずL km（mはブロックサイズ）のすべての項目を調べ、検索キーよりも大きい項目が見つかるまで繰り返します。リスト内の検索キーの正確な位置を見つけるために、サブリストL [( k -1) m , km ]に対して線形探索が実行されます。
mの最適値は√ nです。ここでnはリストLの長さです。アルゴリズムのどちらのステップも最大√ n個の項目を参照するため、アルゴリズムの実行時間は O( √ n ) です。これは線形探索よりも優れていますが、二分探索よりも劣っています。二分探索に対する利点は、ジャンプ探索では後方へのジャンプが1回だけであるのに対し、二分探索では最大 log n回後方にジャンプできることです。これは、後方へのジャンプが前方へのジャンプよりも大幅に時間がかかる場合に重要になります。
このアルゴリズムは、最終的に線形探索を実行する前に、サブリストに対して複数レベルのジャンプ探索を実行することで変更できます。k レベルのジャンプ探索の場合、l番目のレベル（1 から数える）の最適なブロックサイズm lはn (kl)/kです。修正されたアルゴリズムはk回の後方ジャンプを実行し、実行時間は O( kn 1/( k +1) ) になります。
実装
アルゴリズムJumpSearch の入力は
、順序付きリストL、その長さn、検索キーsです。
出力は、L内のsの位置、sがLにない場合は何も出力されません。
a ← 0
b ← ⌊√n ⌋
L min( b , n )-1 < s の間、a ← b b ← b + ⌊√ n ⌋
を実行し、
a ≥ nの場合は何も返さない。
L a < s の場合、a ← a + 1
を実行し、
a = min( b , n )
の場合は何も返さない。
L a = s の場合はaを返し、そうでない場合は
何も返さない
参照
- ジャンプポイント検索
- スキップリスト
- 補間検索
- 線形探索- O( n )時間で実行され、前方のみを探索する
- バイナリ検索- O(log n )時間で実行され、前方と後方の両方を参照します
参考文献
この記事には、Paul E. Blackのパブリックドメイン資料が含まれています。「ジャンプ検索」。アルゴリズムとデータ構造の辞書。NIST 。- Ben Shneiderman、「ジャンプ検索：高速シーケンシャル検索テクニック」、CACM、21(10):831-834、1978年10月。
