ジャンプ探索（Jump Search）とは？目的の範囲に到達したら線形探索を行う方法！

アルゴリズム

2025.03.06

この記事では

線形探索（Linear Search）とは
コードで示す具体例
コードの解説

を紹介していきます。

探索アルゴリズム全般について知りたい方はこちら！

ジャンプ探索（Jump Search）とは
まとめ

ジャンプ探索（Jump Search）とは

説明: ソートされた配列に対して、一定のステップサイズでジャンプしながら探索し、目的の範囲に到達したら線形探索を行う方法です。
時間計算量: 最悪の場合 $O (n)$ 。
使用例: ソートされたデータセットで、二分探索よりも効率的な場合。

現実の例にすると

「辞書で単語を探す（ジャンプしながら）」

例えば、辞書で特定の単語を探しているとします。ジャンプ探索では、まず辞書のページを一定の間隔（例えば10ページごと）でジャンプしながら確認します。目的の単語がそのページにない場合、次のジャンプを行います。もしジャンプしたページを超えてしまった場合、その前のジャンプから1ページずつ戻って確認します。

このようにして、効率的に単語を見つけることができます。

具体例：ソートされたリストから特定の値を探す

例えば、ソートされたリスト [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] から値 13 を探す場合を考えます。

コード例（Python）

import math

def jump_search(arr, target):
    length = len(arr)
    jump = int(math.sqrt(length))
    left, right = 0, 0
    
    while left < length and arr[left] <= target:
        right = min(length - 1, left + jump)
        if arr[left] <= target <= arr[right]:
            break
        left += jump
    
    if left >= length or arr[left] > target:
        return -1
    
    for i in range(left, right + 1):
        if arr[i] == target:
            return i
    
    return -1

# 使用例
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 13
result = jump_search(arr, target)

if result != -1:
    print(f"ターゲット {target} はインデックス {result} にあります。")
else:
    print("ターゲットが見つかりませんでした。")

コードの解説

必要なモジュールのインポート:
```
import math
```
math モジュールをインポートして、平方根の計算に使用します。
関数定義:
```
def jump_search(arr, target):
```
jump_search という名前の関数を定義しています。この関数は、ソートされたリスト arr の中から target を探します。
初期化:
```
length = len(arr)
jump = int(math.sqrt(length))
left, right = 0, 0
```
リストの長さ length を取得し、ジャンプ幅 jump をリストの長さの平方根に設定します。探索範囲の左端 (left) と右端 (right) を初期化します。
ジャンプ探索:
```
while left < length and arr[left] <= target:
    right = min(length - 1, left + jump)
    if arr[left] <= target <= arr[right]:
        break
    left += jump
```
リストの範囲内で、かつ現在の位置の値がターゲット以下である限り、ジャンプ幅ごとに探索を進めます。ターゲットが現在の範囲内にある場合、ループを抜けます。
ターゲットが見つからない場合:
```
if left >= length or arr[left] > target:
    return -1
```
探索範囲がリストの範囲外に出るか、現在の位置の値がターゲットより大きい場合、-1 を返します。
線形探索:
```
for i in range(left, right + 1):
    if arr[i] == target:
        return i
```
ジャンプ範囲内で線形探索を行い、ターゲットが見つかった場合、そのインデックスを返します。
ターゲットが見つからない場合:
```
return -1
```
線形探索が終了してもターゲットが見つからない場合、-1 を返します。
使用例:
```
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 13
result = jump_search(arr, target)
```
ソートされたリスト arr と探したい値 target を定義し、jump_search 関数を呼び出します。
結果の表示:
```
if result != -1:
    print(f"ターゲット {target} はインデックス {result} にあります。")
else:
    print("ターゲットが見つかりませんでした。")
```
関数の結果に基づいて、ターゲットが見つかった場合はそのインデックスを表示し、見つからなかった場合はメッセージを表示します。