【初心者向け】二分探索（バイナリサーチ）をわかりやすく解説！

プログラミングを学び始めると、さまざまなアルゴリズムに出会います。その中でも、特に重要で効率的な探索アルゴリズムの一つが「二分探索（にぶんたんさく）」、別名「バイナリサーチ」です。

この記事では、二分探索とは何か、どのような仕組みで動くのか、そしてどのように便利なのかを、初心者の方にも理解しやすいように解説していきます。

二分探索は、あらかじめソート（整列）されたデータの中から、目的の値を見つけ出すための高速な探索アルゴリズムです。 身近な例で言えば、分厚い辞書や電話帳から特定の単語や名前を探すときの動作に似ています。

いきなり最初のページから順番に探すのではなく、まず真ん中あたりを開き、目的の単語がそのページより前にあるか後ろにあるかを確認します。そして、探す必要のない半分を無視し、残りの半分でまた同じことを繰り返します。この「範囲を半分に絞り込んでいく」という点が、二分探索の最大の特徴です。

二分探索は、以下の手順を繰り返して目的の値を探します。

1. 探索範囲の中央の要素を見つけます。
2. 中央の要素と探したい値を比較します。
3. • もし一致すれば、探索は成功です。その位置を返して終了します。
   • 探したい値が中央の要素より小さい場合、探索範囲を前半部分（左半分）に絞り込みます。
   • 探したい値が中央の要素より大きい場合、探索範囲を後半部分（右半分）に絞り込みます。
4. 探索範囲がなくなるまで、または値が見つかるまで上記の手順を繰り返します。

このプロセスにより、1回の比較で探索範囲が半分になるため、データが非常に多くても、ごくわずかな回数で目的の値を見つけ出すことができます。

探索アルゴリズムとして最もシンプルなものに「線形探索（せんけいたんさく）」があります。これは、データの先頭から順番に一つずつ値を確認していく方法です。

二分探索がいかに効率的かを理解するために、線形探索と比較してみましょう。

実際にPythonで二分探索を実装するコードを見てみましょう。

def binary_search(sorted_list, target): left = 0 right = len(sorted_list) - 1 while left <= right: mid = (left + right) // 2 # 探索範囲の中央のインデックスを計算 # 中央の値とターゲットを比較 if sorted_list[mid] == target: return mid # 値が見つかった場合、そのインデックスを返す elif sorted_list[mid] < target: left = mid + 1 # ターゲットが中央値より大きい場合、探索範囲を右半分に絞る else: right = mid - 1 # ターゲットが中央値より小さい場合、探索範囲を左半分に絞る return -1 # 値が見つからなかった場合
# --- 実行例 ---
my_list =
target_value = 70
result_index = binary_search(my_list, target_value)
if result_index != -1: print(f"値 {target_value} は、インデックス {result_index} に見つかりました。")
else: print(f"値 {target_value} はリスト内に見つかりませんでした。")

二分探索は、単に特定の値を探すだけでなく、より広い意味での「問題解決」にも応用されます。

• データベース検索: 大量のデータが格納されているデータベースシステムでは、特定のレコードを高速に検索するために内部的に二分探索に近いアルゴリズムが使われています。
• 最適化問題: 「ある条件を満たす最小値（または最大値）は何か？」といった問題にも応用できます。 例えば、特定の性能を達成するために必要な最低限のパラメータを見つける、といった場面で活用されます。
• デバッグ: プログラムのどこでバグが発生したかを特定する際にも、二分探索の考え方が役立ちます。コードの真ん中にチェックポイントを置き、問題が前半で起きたか後半で起きたかを確認していくことで、効率的に原因箇所を絞り込めます。