二分探索（Binary Search）とは？探索範囲を半分に絞り込む方法！

アルゴリズム

2025.03.06

この記事では

二分探索（Binary Search）とは
コードで示す具体例
コードの解説

を紹介していきます。

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

二分探索（Binary Search）とは
まとめ

二分探索（Binary Search）とは

説明: ソートされた配列やリストに対して、中央の要素と比較し、目的の要素が中央よりも小さいか大きいかを判断して探索範囲を半分に絞り込む方法です。これを繰り返して目的の要素を見つけます。
時間計算量: 最悪の場合 $O (log n)$ 。
使用例: ソートされたデータセット。

現実の例にすると

「辞書で単語を探す」

例えば、辞書で特定の単語を探しているとします。辞書はアルファベット順に並んでいるので、まず辞書の真ん中あたりを開きます。探している単語がそのページにない場合、単語がそのページより前にあるか後にあるかを確認します。もし後にあるなら、辞書の後半部分をさらに半分に分けて再度探します。

このプロセスを繰り返して、探している単語にたどり着くまで範囲を絞り込んでいきます。

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

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

コード例（Python）

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

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

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

コードの解説

関数定義:
```
def binary_search(arr, target):
```
binary_search という名前の関数を定義しています。この関数は、ソートされたリスト arr の中から target を探します。
初期化:
```
left, right = 0, len(arr) - 1
```
探索範囲の左端 (left) と右端 (right) を初期化します。left はリストの最初のインデックス（0）、right はリストの最後のインデックス（len(arr) - 1）です。
ループ:
```
while left <= right:
```
left が right 以下である限り、ループを続けます。探索範囲が有効である間、ループが実行されます。
中間点の計算:
```
mid = (left + right) // 2
```
現在の探索範囲の中間点 (mid) を計算します。// は整数除算を意味します。
ターゲットの比較:
```
if arr[mid] == target:
    return mid
elif arr[mid] < target:
    left = mid + 1
else:
    right = mid - 1
```
- arr[mid] == target：中間点の値がターゲットと一致する場合、そのインデックス mid を返します。
- arr[mid] < target：中間点の値がターゲットより小さい場合、探索範囲を右半分に絞り込みます（left を mid + 1 に更新）。
- arr[mid] > target：中間点の値がターゲットより大きい場合、探索範囲を左半分に絞り込みます（right を mid - 1 に更新）。
ターゲットが見つからない場合:
```
return -1
```
ループが終了してもターゲットが見つからない場合、-1 を返します。
使用例:
```
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7
result = binary_search(arr, target)
```
ソートされたリスト arr と探したい値 target を定義し、binary_search 関数を呼び出します。
結果の表示:
```
if result != -1:
    print(f"ターゲット {target} はインデックス {result} にあります。")
else:
    print("ターゲットが見つかりませんでした。")
```
関数の結果に基づいて、ターゲットが見つかった場合はそのインデックスを表示し、見つからなかった場合はメッセージを表示します。