補間探索（Interpolation Search）とは？目的の要素の位置を補間して探索する方法！

アルゴリズム

2025.03.06

この記事では

補間探索（Interpolation Search）とは
コードで示す具体例
コードの解説

を紹介していきます。

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

補間探索（Interpolation Search）とは
まとめ

補間探索（Interpolation Search）とは

説明: ソートされた配列に対して、目的の要素の位置を補間して探索する方法です。データが均等に分布している場合に効果的です。
時間計算量: 最悪の場合 $O (n)$ 、平均 $O (log log n)$ 。
使用例: 均等に分布したソートされたデータセット。

現実の例にすると

「本棚で特定の本を探す（本の高さを考慮して）」

例えば、本棚に並んでいる本の中から特定の本を探しているとします。補間探索では、本の高さや厚さなどの情報を利用して、目的の本がどのあたりにあるかを予測します。例えば、探している本が薄い本であれば、薄い本が多く並んでいるエリアを重点的に探します。

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

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

例えば、ソートされたリスト [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] から値 70 を探す場合を考えます。

コード例（Python）

def interpolation_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high and arr[low] <= target <= arr[high]:
        if low == high:
            if arr[low] == target:
                return low
            return -1
        
        # 補間の計算
        pos = low + ((target - arr[low]) * (high - low) // (arr[high] - arr[low]))

        if arr[pos] == target:
            return pos
        if arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1

    return -1

# 使用例
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
target = 70
result = interpolation_search(arr, target)

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

コードの解説

関数定義:
```
def interpolation_search(arr, target):
```
interpolation_search という名前の関数を定義しています。この関数は、ソートされたリスト arr の中から target を探します。
初期化:
```
low = 0
high = len(arr) - 1
```
探索範囲の左端 (low) と右端 (high) を初期化します。
ループ:
```
while low <= high and arr[low] <= target <= arr[high]:
```
low が high 以下であり、かつ target が arr[low] と arr[high] の間にある限り、ループを続けます。
単一要素のチェック:
```
if low == high:
    if arr[low] == target:
        return low
    return -1
```
探索範囲が単一要素になった場合、その要素がターゲットと一致するかを確認します。一致すればそのインデックスを返し、一致しなければ -1 を返します。

補間の計算:

pos = low + ((target - arr[low]) * (high - low) // (arr[high] - arr[low]))

補間の計算を行い、推定位置 pos を求めます。

ターゲットの比較:
```
if arr[pos] == target:
    return pos
if arr[pos] < target:
    low = pos + 1
else:
    high = pos - 1
```
- arr[pos] == target：推定位置の値がターゲットと一致する場合、そのインデックス pos を返します。
- arr[pos] < target：推定位置の値がターゲットより小さい場合、探索範囲を右半分に絞り込みます（low を pos + 1 に更新）。
- arr[pos] > target：推定位置の値がターゲットより大きい場合、探索範囲を左半分に絞り込みます（high を pos - 1 に更新）。
ターゲットが見つからない場合:
```
return -1
```
ループが終了してもターゲットが見つからない場合、-1 を返します。
使用例:
```
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
target = 70
result = interpolation_search(arr, target)
```
ソートされたリスト arr と探したい値 target を定義し、interpolation_search 関数を呼び出します。
結果の表示:
```
if result != -1:
    print(f"ターゲット {target} はインデックス {result} にあります。")
else:
    print("ターゲットが見つかりませんでした。")
```
関数の結果に基づいて、ターゲットが見つかった場合はそのインデックスを表示し、見つからなかった場合はメッセージを表示します。