二分探索 | 応用情報技術者試験
二分探索とは
二分探索（Binary Search / バイナリサーチ）とは、あらかじめ昇順または降順に並べ替え（ソート）されているデータ群から、目的のデータを素早く見つけるためのアルゴリズムです。データ全体の中央にある値を確認し、目的の値がそれより「大きいか」「小さいか」を判断します。それによって探索範囲を半分（二分）に絞り込むことを繰り返し、高速に目的地に到達します。
具体例
国語辞書で「さくら」という言葉を探すとき、まず本のちょうど真ん中のページを開き、そこが「た行」であれば「さ行」はそれより前にあると判断して、前半部分の真ん中を開く、というように範囲を半分ずつに狭めていく作業です。
# 二分探索のプログラム例
def binary_search(sorted_list, target):
low, high = 0, len(sorted_list) - 1
while low <= high:
mid = (low + high) // 2
if sorted_list[mid] == target:
return mid # 見つかった！
elif sorted_list[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
もう少し詳しく