二分探索とは
二分探索（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もう少し詳しく
二分探索（Binary Search / バイナリサーチ）は、あらかじめ昇順または降順に整列（ソート）されている配列から、目的のデータを高速に検索するアルゴリズムです。探索手順は以下の通りです。まず、探索範囲の中央にある要素の値と、目的の値を比較します。もし一致すればそこで探索は終了です。もし目的の値の方が小さければ、中央より右側には存在しないと判断できるため、探索範囲を「左半分」に絞り込みます。逆に大きければ「右半分」に絞り込みます。この手順を、探索範囲が空になるか目的の値が見つかるまで繰り返します。1回の比較ごとに探索範囲が正確に「半分」になるため、データ数がどれほど多くなっても極めて高速に処理できます。データ数がN個のとき、最悪でも約log2(N)回の比較で探索が完了します（計算量はO(log N)）。例えば、40億個のデータがあっても、わずか32回程度の比較で目的のデータを見つけることができます。ただし、事前にデータが完全に整列していること、およびインデックスによる直接アクセス（ランダムアクセス）が可能な「配列」構造であることが適用条件となります。
試験でのポイント
試験では、二分探索の計算量（O(log N)）に関する計算や、線形探索（O(N)）との性能差を問う問題が非常によく出題されます。また、二分探索のプログラムコードの空欄を埋めさせる問題も頻出であり、特に中央位置（mid）を計算する式や、次の探索範囲を定義する際の境界値の設定（low = mid + 1 や high = mid - 1）において、境界値の重複や無限ループを防ぐための細かい条件指定が問われます。
関連する用語
O(log N)（計算量がデータの対数に比例して増加する非常に効率の良いオーダー）、ソート（データを特定の順序に並び替える処理）、ランダムアクセス（インデックスを指定して任意の場所に直接アクセスすること）。