Overview
二分探索（Binary Search） は、ソート済みの配列 に対して高速に探索を行うアルゴリズム。
通常の線形探索に比べ、大規模なデータセットでも効率的に処理できる。
1.二分探索の基本
2.Python の bisect モジュール
3.二分探索の応用
4.典型問題を解いてみる
1. 二分探索の基本
(1) 二分探索の考え方
- 配列が ソートされていること が前提
- 中央の要素
midとkeyを比較
midがkeyより大きければ、左側を探索
midがkeyより小さければ、右側を探索
探索範囲を半分にするので $O(log N)$ で探索可能
(2) 二分探索の基本実装（再帰版）
def binary_search(arr, key, left, right):
if left > right:
return -1 # 見つからなかった場合
mid = (left + right) // 2 # 中央のインデックス
if arr[mid] == key:
return mid # 見つかった
elif arr[mid] > key:
return binary_search(arr, key, left, mid - 1) # 左側を探索
else:
return binary_search(arr, key, mid + 1, right) # 右側を探索
(3) 二分探索の基本実装（反復版）
def binary_search_iterative(arr, key):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == key:
return mid # 見つかった
elif arr[mid] > key:
right = mid - 1 # 左側を探索
else:
left = mid + 1 # 右側を探索
return -1 # 見つからなかった
- 再帰版と反復版はどちらも $O(log N)$
- 反復版の方がスタックオーバーフローのリスクがないため実用的
2.Python の bisect モジュール
Python では bisect を使うと、二分探索を簡単に実装できます。
import bisect
arr = [1, 3, 5, 7, 9]
x = 5
index = bisect.bisect_left(arr, x) # 5 が存在する最小の位置
print(index) # 2
| 関数 | 説明 |
|---|---|
bisect_left(arr, x) |
x を挿入できる最小のインデックス |
bisect_right(arr, x) |
x を挿入できる最大のインデックス |
insort_left(arr, x) |
x を arr にソート済みで挿入 |
-bisect_left は二分探索の lower_bound に相当
-bisect_right は upper_bound に相当
3.二分探索の応用
(1) 最初に出現する位置を探す（lower_bound）
import bisect
arr = [1, 2, 2, 3, 3, 3, 4, 5]
x = 3
index = bisect.bisect_left(arr, x) # 3 が最初に出現するインデックス
print(index) # 3
-
bisect_leftを使うと 指定した値の最初の出現位置を取得
(2) 最後に出現する位置を探す（upper_bound）
index = bisect.bisect_right(arr, x) # 3 の次の位置
print(index - 1) # 5
-
bisect_right - 1を使うと 指定した値の最後の出現位置を取得
4. 典型問題を解いてみる
例題1. 二分探索で値を探す
問題: N 個の整数 A から Q 個のクエリ X に対し、X が存在するか判定せよ。
回答
import bisect
N, Q = map(int, input().split())
A = sorted(map(int, input().split()))
for _ in range(Q):
X = int(input())
idx = bisect.bisect_left(A, X)
print("Yes" if idx < N and A[idx] == X else "No")
例題2. 最小の X を求める
問題: N 個の整数 A がソートされている。A[i] >= X となる最小の i を求めよ。
回答
import bisect
N, X = map(int, input().split())
A = sorted(map(int, input().split()))
idx = bisect.bisect_left(A, X)
print(idx if idx < N else -1)
例題3. ある範囲内の要素の個数
問題: N 個の整数 A に対し、区間 [L, R] に含まれる要素の個数を求めよ。
回答
import bisect
N, Q = map(int, input().split())
A = sorted(map(int, input().split()))
for _ in range(Q):
L, R = map(int, input().split())
left_idx = bisect.bisect_left(A, L)
right_idx = bisect.bisect_right(A, R)
print(right_idx - left_idx)
例題4. 最も近い値を探す
問題: N 個の整数 A が与えられ、各 Q 個のクエリ X に対し、最も近い値を求めよ。
回答
import bisect
N, Q = map(int, input().split())
A = sorted(map(int, input().split()))
for _ in range(Q):
X = int(input())
idx = bisect.bisect_left(A, X)
candidates = []
if idx < N:
candidates.append(A[idx])
if idx > 0:
candidates.append(A[idx - 1])
print(min(candidates, key=lambda v: abs(v - X)))