しろーぬなずな が に投稿

二分探索（バイナリサーチ）は、あらかじめ昇順または降順にソート（整列）されたリストの中から、特定の値を高速に探し出すためのアルゴリズムである。

日常的な例でいうと、辞書で「こんぱす」という単語を調べるとき、最初のページから1ページずつめくる（線形探索）のではなく、まず真ん中あたりを開き、そこが「さ行」なら「もっと前だな」、「た行」なら「もっと後ろだな」と判断して探す範囲を狭めていく。この直感的な探し方こそが「二分探索」の正体である。

1. 二分探索の仕組み（例示）

例えば、次のように昇順にソートされた9個の要素を持つリストから、ターゲットとなる数値 23 を探すケースを考える。

リスト: [3, 8, 12, 17, 23, 29, 35, 42, 50] (要素数 $N = 9$)

  1. 初期状態
    • 探索範囲の左端（始端）のインデックス left = 0 （値: 3）
    • 探索範囲の右端（終端）のインデックス right = 8 （値: 50）
  2. ステップ1
    • 中央のインデックス mid = (left + right) // 2 = 4 を計算。
    • mid の値は 23（インデックス 4 の要素）。
    • 探していた値 23 と一致したため、ここで探索成功。

もしターゲットが 42 だった場合は以下のようになる。

  1. ステップ1
    • 中央 mid = 4 (値: 23) を確認。
    • 42 は 23 より大きいため、インデックス 4 以下の範囲には存在しないと判断できる。
    • 探索範囲を右半分に絞り込むため、left = mid + 1 = 5 に更新する。
  2. ステップ2
    • 新しい探索範囲はインデックス 5 〜 8。
    • 新たな中央 mid = (5 + 8) // 2 = 6 (値: 35) を確認。
    • 42 は 35 より大きいため、さらに右半分に絞り込む。left = mid + 1 = 7 に更新。
  3. ステップ3
    • 新しい探索範囲はインデックス 7 〜 8。
    • 新たな中央 mid = (7 + 8) // 2 = 7 (値: 42) を確認。
    • ターゲットと一致したため、探索成功（インデックス 7）。

このように、1ステップごとに探索範囲が半分（2分の1）になるため、要素数が非常に多くても極めて高速に探索できる。 計算量は $O(\log N)$ となり、仮に要素数が100万個あっても、わずか20回程度の比較で目的の値を見つけることができる。

2. Pythonでの実装例

Pythonで二分探索を実装する場合、「自分でループを書いて実装する方法」と、「標準ライブラリの bisect を使う方法」の2通りがある。

① ループによる手動実装（基本形）

def binary_search(arr, target):    left = 0    right = len(arr) - 1    while left <= right:        mid = (left + right) // 2        if arr[mid] == target:            return mid  # 見つかった場合はインデックスを返す        elif arr[mid] < target:            left = mid + 1  # 右半分に絞る        else:            right = mid - 1  # 左半分に絞る    return -1  # 見つからなかった場合 # テスト data = [3, 8, 12, 17, 23, 29, 35, 42, 50] print(binary_search(data, 23))  # 出力: 4 print(binary_search(data, 10))  # 出力: -1

② Python標準ライブラリ bisect の利用

Pythonには二分探索を行うための強力なライブラリ bisect が標準で用意されている。実戦（競技プログラミングなど）ではこちらを使うことが多い。

import bisect data = [3, 8, 12, 17, 23, 29, 35, 42, 50] # 指定した値（23）をソート順を崩さずに挿入できる最も左側の位置を取得 index = bisect.bisect_left(data, 23) print(index)  # 出力: 4 # 存在しない値（10）を指定した場合 # 10を挿入すべき位置（8と12の間、すなわちインデックス2）が返る index_not_found = bisect.bisect_left(data, 10) print(index_not_found)  # 出力: 2

3. AtCoderで二分探索を学ぼう！

二分探索の理解を深めるために最適な、AtCoderの練習問題を紹介する。 簡単なものから、少し応用が必要なものへとステップアップできるように配置している。

※注意：以下は問題のネタバレ（アプローチ方法や解法のヒント）を含みます。また、二分探索であるということが分かってしまいます。AtCoderの過去問を、初見で解きたい方は、以降を読まないことを推奨します。

① 【超基本】典型アルゴリズム A - 二分探索

まずは二分探索そのものの動作をコードに落とし込む練習から。

  • 問題リンク: 典型アルゴリズム A - 二分探索
  • 概要: $N$ 個の昇順に並んだ配列 $A$ の中から、$A_i \ge K$ を満たす最小のインデックス $i$ を求める。
  • ヒント: Pythonの bisect_left を使うと1行でAC（正解）できるが、ライブラリを使わずに自作の二分探索ループを書いて通してみるのも、非常に良い練習になる。

② 【基本の応用】ABC 212 C - Min Difference

2つの配列同士を比較する際に二分探索を組み合わせる問題。

  • 問題リンク: ABC 212 C - Min Difference
  • 概要: 2つの配列 $A$ と $B$ から1つずつ要素を選び、その差の絶対値の最小値を求める。
  • ヒント: 2重ループで全探索すると $O(N^2)$ でタイムアウト（TLE）になる。そこで、片方の配列 $B$ を事前にソートしておき、配列 $A$ の各要素 $A_i$ に対して「$B$ の中で $A_i$ に最も近い値」を二分探索で探すようにすると、全体の計算量を $O(N \log N)$ に削減できる。

③ 【答えを二分探索】ABC 146 C - Buy an Integer

「配列からの探索」ではなく、「条件を満たす最大（最小）の値を二分探索で探す」という、通称 「めぐる式二分探索」 の大定番問題。

  • 問題リンク: ABC 146 C - Buy an Integer
  • 概要: 予算 $X$ 円以内で購入できる最大の整数 $N$ （$1$ 以上 $10^9$ 以下）を求める。
  • ヒント: 整数 $N$ を $1$ から順に試すと、最悪 $10^9$ 回のループが必要になり間に合わない。しかし、「整数 $N$ を買うことができるか？」という判定は、「$N$ が大きくなれば価格も高くなる（単調性がある）」ため二分探索が適用できる。
    • OK（買える領域）と NG（買えない領域）の境界線を二分探索で狭めていくアプローチを取る。

④ 【3要素の組み合わせ】ABC 077 C - Snuke Festival

二分探索を複数回組み合わせる、非常に教育的な中級問題。

  • 問題リンク: ABC 077 C - Snuke Festival
  • 概要: 3つの配列 $A, B, C$ からそれぞれ要素を1つずつ選び、$A_i < B_j < C_k$ となる組み合わせの総数を求める。
  • ヒント: 真ん中となる $B$ の要素 $B_j$ を1つ固定して考える。
    • $A$ の中から $B_j$ より小さい要素の数を二分探索で探す（bisect_left）。
    • $C$ の中から $B_j$ より大きい要素の数を二分探索で探す（bisect_right）。
    • それぞれ見つけた個数を掛け合わせ、すべての $B_j$ について足し合わせれば答えになる。

二分探索は、アルゴリズムの実装力を問われるコンテストにおいて、避けては通れない最重要テクニックの一つである。

  • コメントを投稿するにはログインしてください