二分探索

二分探索

二分探索 は、データ数が増えても 高速に検索 することができるアルゴリズムです。

辞書や電話帳から探すときに似た方法で、目的の値がそれよりも 前か後ろか を判断して探す方法です。

データは昇順に並んでいる必要があります。

ソースコード

二分探索 では、昇順に並んでいるデータの中から目的のデータが、真ん中より右にあるか左にあるかを調べる作業を繰り返します。

実装すると下記のようなソースになります。

リストの左端と右端から、探す位置を半分に絞り込みながら順に検索しています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def binary_search(data, value):
    left = 0                      # 検索する範囲の左側を設定
    right = len(data) - 1         # 検索する範囲の右側を設定
    while left <= right:          # 検索する範囲がなくなるまで実行
        mid = (left + right) // 2 # 検索する範囲の中央の値を算出
        if data[mid] == value:    # 中央の値と一致した場合
            return mid            # その位置を返す
        elif data[mid] < value:   # 中央の値より大きい場合
            left = mid + 1        # 検索範囲の左側を移動
        else:                     # 中央の値より小さい場合
            right = mid - 1       # 検索範囲の右側を移動
    return -1                     # 見つからなかったので-1を返す

data = [10,20,30,40,50,60,70,80,90]

print('値が見つかるケース１ =>', binary_search(data,80))
print('値が見つかるケース２ =>', binary_search(data,20))
print('値が見つかるケース３ =>', binary_search(data,60))
print('値が見つからないケース１ =>', binary_search(data,9))
print('値が見つからないケース２ =>', binary_search(data,23))
print('値が見つからないケース３ =>', binary_search(data,91))

[実行結果]

値が見つかるケース１ => 7
値が見つかるケース２ => 1
値が見つかるケース２ => 5
値が見つからないケース１ => -1
値が見つからないケース２ => -1
値が見つからないケース３ => -1

値が見つかった場合はその インデックス を、見つからなかった場合は -1 を返すことを確認できました。