Overview
二分探索（Binary Search）は、ソート済み配列に対し探索範囲を半分に絞っていく高速な探索手法。
探索時間は O(log N) で、線形探索より桁違いに高速。
1.二分探索の基本
2.bisect モジュール(Python)
3.二分探索の応用
4.典型問題を解いてみる
1. 二分探索の基本
(1) 二分探索とは
ソートされた配列から目的の値を高速に探す方法。
手順：
- 範囲の中央（mid）を見る
- target と比較して、左 or 右どちらか半分を捨てる
- 残った方を同じように調べる
→ この繰り返し
時間計算量：O(log N)
データ数 N=100万でもたった 20 回の比較で済む。
(2) 二分探索の条件
2分探索を使うには以下が必須：
✔ データがソート済みである
✔ 単調性（区間が連続 or 一方向に進む性質）
✔ 探索条件が Yes/No で判定できる
(3) 二分探索の基本実装
def binary_search(arr, target):
left, right = 0, 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
(4) 二分探索が必要になる典型パターン
✦ パターン1：配列内の検索（基本）
配列に target が存在するか
最初/最後の位置を知りたいとき。
✦ パターン2：答えが数値で 単調 なとき（典型的競プロパターン）
例：「条件を満たす最小の X を求める」
- X 以下で買える商品数
- 時間 T 以内に終わる人数
- 距離 D 以上離せる？
- Y 本切り出せる最小の長さ L
など。
✦ パターン3：Yes/No 判定 × 単調性（判定関数型）
def is_ok(x):
return 条件
left, right = NG, OK
while abs(left - right) > 1:
mid = (left + right) // 2
if is_ok(mid):
right = mid
else:
left = mid
return right
2.bisect モジュール（Python）
Python では bisect を使うと、二分探索を簡単に実装できる。
bisect は内部でC実装の二分探索が使われており $O(log N)$ の高速処理が可能。
import bisect
bisect.bisect_left(arr, x) # lower_bound
bisect.bisect_right(arr, x) # upper_bound
使用例：
arr = [1, 2, 2, 3, 5]
print(bisect.bisect_left(arr, 2)) # 1
print(bisect.bisect_right(arr, 2)) # 3
| 関数 | 説明 |
|---|---|
bisect_left(arr, x) |
x を挿入できる最小のインデックス |
bisect_right(arr, x) |
x を挿入できる最大のインデックス |
insort_left(arr, x) |
x を arr にソート済みで挿入 |
3.二分探索の応用
(1) 最初に出現する位置を探す（lower_bound）
def lower_bound(arr, x):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < x:
left = mid + 1
else:
right = mid
return left
-
bisect_leftを使うと 指定した値の最初の出現位置を取得
(2) 最後に出現する位置を探す（upper_bound）
def upper_bound(arr, x):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] <= x:
left = mid + 1
else:
right = mid
return left
-
bisect_right - 1を使うと 指定した値の最後の出現位置を取得
4. 典型問題を解いてみる
例題1. 標準的な二分探索
問題: 配列 A 内に target が存在するか？
回答
def binary_search(arr, x):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return True
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return False
例題2. 値 X が配列 A に何個含まれるかを求める（bisect の基本）
問題: 整数 N と、昇順ソート済みの整数配列 A（長さ N）、そして整数 X が与えられる。
A の中に 値 X が何個含まれるか を二分探索（bisect）を使って求めよ。
回答
import bisect
N = int(input())
A = list(map(int, input().split()))
X = int(input())
# A はソート済みという前提
left = bisect.bisect_left(A, X)
right = bisect.bisect_right(A, X)
print(right - left)
例題3. 「判定関数を使った」二分探索（典型パターン）
問題: 長さ N の棒が複数ある。
これらの棒を長さ L で切り分けると、合計で M 本以上作れるかがわかる。
条件「長さ L で M 本以上作れる」を満たす 最大の L を求めよ。
（いわゆる「答えが数値」の二分探索の典型問題）
回答
# 入力
N, M = map(int, input().split())
A = list(map(int, input().split())) # 各棒の長さ
# 判定関数: 長さ x で M 本以上切り出せるか？
def is_ok(x):
return sum(a // x for a in A) >= M
left, right = 0, max(A) + 1 # L の範囲（right は常に OK）
while right - left > 1:
mid = (left + right) // 2
if is_ok(mid):
left = mid # mid は可能 → もっと大きくできるか探す
else:
right = mid # mid は不可 → 小さくする
print(left) # 最大の L