ジャンプ検索（Jump Search）とは？仕組み・計算量・C++実装例をわかりやすく解説

ジャンプ検索（Jump Search）の概要

ジャンプ検索は、ソート済み（整列済み）リストに対して有効な探索アルゴリズムの一つです。リストを一定サイズの「ブロック」に区切り、まず目的の要素が存在するブロックを大まかに特定します。そのブロックに要素が見つからなければ、ブロック全体を次の範囲へとずらしながら探索を進めていきます。

ブロックサイズはリストの長さをもとに決定され、リストのサイズを n とすると、ブロックサイズは √n となります。適切なブロックを特定した後は、その範囲内で線形探索（リニアサーチ）を用いて要素を正確に見つけ出します。

探索性能の面では、ジャンプ検索は線形探索 O(n) と二分探索 O(log n) の中間に位置づけられます。二分探索ほど高速ではありませんが、前進のみで探索できるため、連結リストなど後方へのジャンプが苦手なデータ構造でも利用しやすいのが特徴です。

ジャンプ検索の計算量

• 時間計算量：O(√n)
• 空間計算量：O(1)

なお、ブロックサイズを √n とすると、「ジャンプ回数」と「ブロック内の線形探索回数」の合計が最小になることが知られており、これが理論上最適なブロックサイズとされています。

前提条件

ジャンプ検索を使用するためには、対象となる配列が昇順にソートされている必要があります。未ソートのデータには適用できない点に注意してください。

入力と出力

Input:
A sorted list of data:
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
The search key 356
Output:
Item found at location: 11

アルゴリズム

jumpSearch(array, size, key)

入力： ソート済みの配列、配列のサイズ、検索キー

出力： キーが見つかった場合はその位置（インデックス）、見つからない場合は無効な値（-1）

Begin
    blockSize := √size
    start := 0
    end := blockSize
    while array[end] <= key AND end < size do
        start := end
        end := end + blockSize
        if end > size − 1 then
            end := size
    done
    for i := start to end -1 do
        if array[i] = key then
            return i
    done
    return invalid location
End

処理の流れ

1. ブロックサイズを √size として設定し、探索範囲の始点 start と終点 end を初期化します。
2. end 番目の要素がキー以下である間、start と end を1ブロックぶん前方へ移動させます。これにより、キーが含まれ得るブロックを絞り込みます。
3. end が配列の末尾を超えた場合は、end を配列サイズに丸めます。
4. 特定したブロック [start, end) 内を線形探索し、キーと一致する要素があればそのインデックスを返します。
5. 最後まで見つからなければ、無効な値を返して終了します。

C++による実装例

#include<iostream>
#include<cmath>

using namespace std;
int jumpSearch(int array[], int size, int key) {
    int start = 0;
    int end = sqrt(size); // 配列長の平方根

    while(array[end] <= key && end < size) {
        start = end; // 適切なブロックでなければブロックを前方へ移動
        end += sqrt(size);
        if(end > size - 1)
            end = size; // 右端が範囲を超えたら境界内に収める
    }

    for(int i = start; i<end; i++) { // 選択したブロック内で線形探索を実行
        if(array[i] == key)
            return i; // キーが存在する正しい位置
    }
    return -1;
}

int main() {
    int n, searchKey, loc;
    cout << "Enter number of items: ";
    cin >> n;
    int arr[n]; // サイズ n の配列を作成
    cout << "Enter items: " << endl;

    for(int i = 0; i< n; i++) {
        cin >> arr[i];
    }

    cout << "Enter search key to search in the list: ";
    cin >> searchKey;
    if((loc = jumpSearch(arr, n, searchKey)) >= 0)
        cout << "Item found at location: " << loc << endl;
    else
        cout << "Item is not found in the list." << endl;
}

実行結果

Enter number of items: 20
Enter items:
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
Enter search key to search in the list: 356
Item found at location: 11

この例では、20個のソート済みデータから検索キー「356」を探しています。プログラムはブロック単位でジャンプしながら候補ブロックを絞り込み、インデックス 11 の位置にある要素を正しく検出できていることがわかります。