二分探索
二分探索 は、データ数が増えても 高速に検索 することができるアルゴリズムです。
辞書や電話帳から探すときに似た方法で、目的の値がそれよりも 前か後ろか を判断して探す方法です。
データは昇順に並んでいる必要があります。
ソースコード
二分探索 では、昇順に並んでいるデータの中から目的のデータが、真ん中より右にあるか左にあるかを調べる作業を繰り返します。
実装すると下記のようなソースになります。
リストの左端と右端から、探す位置を半分に絞り込みながら順に検索しています。
[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
data = [10,20,30,40,50,60,70,80,90]
print('値が見つかるケース1 =>', binary_search(data,80)) print('値が見つかるケース2 =>', binary_search(data,20)) print('値が見つかるケース3 =>', binary_search(data,60)) print('値が見つからないケース1 =>', binary_search(data,9)) print('値が見つからないケース2 =>', binary_search(data,23)) print('値が見つからないケース3 =>', binary_search(data,91))
|
[実行結果]
値が見つかるケース1 => 7
値が見つかるケース2 => 1
値が見つかるケース2 => 5
値が見つからないケース1 => -1
値が見つからないケース2 => -1
値が見つからないケース3 => -1
値が見つかった場合はその インデックス を、見つからなかった場合は -1 を返すことを確認できました。