計算量を大幅に縮小できる便利なアルゴリズムとして、二分探索がある。
Pythonではbisectという標準モジュールが便利だが、具体的にどうやって計算しているのかを整理した。
計算量について
平均的な計算回数はlognで、扱うデータ量が多くなればなるほど、その恩恵を受けることができる。
詳細はどこでも説明されているので割愛。
図としてはこんなのをよくみる。

参考：
bisectモジュール
bisectモジュールは配列データの要素の検索と挿入モジュール。
ざっくり三つのメソッドに切り分けられる。
-
一致
-
検索値以上の値が初めて出る箇所
配列の中で最初に2以上の値が出るインデックスは1
-
検索値より大きい値が初めて出る箇所
配列の中で最初に2より大きい値が出るインデックスは3のある4
参考
一致検索, bisect.left, bisect.rightの実装
Gptに聞いて教えてもらっていたが、しばらく理解できなかったので要点をまとめる。
まずはコードを眺める。
def binary_search(arr, x):
left = 0
right = len(arr)-1
while left <= right:
mid = (left + right)//2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid -1
return -1
def lower_bound(arr, x):
left = 0
right = len(arr)
while left < right:
mid = (left + right)//2
if arr[mid] < x:
left = mid + 1
else:
right = mid
return left
def upper_bound(arr, x):
left = 0
right = len(arr)
while left < right:
mid = (left + right)//2
if arr[mid] <= x:
left = mid + 1
else:
right = mid
return left
コード上での違いからは何の差なのか全然わからない
| 関数名 | 最初のrightの値 | 検索の実行条件 | leftとrightを寄せる条件 | rightの寄せ方 |
|---|---|---|---|---|
| binary_search | len(arr) - 1 | left <= right | 等号と不等号は別 | mid - 1 |
| lower_bound | len(arr) | left < right | left を寄せるほうが不等号 | mid |
| upper_bound | len(arr) | left < right | right を寄せるほうが不等号 | mid |
理屈で考えてみる
rightの初期値
ピッタリしないものがある可能性があって、そのためにひと枠増やしておくためにlen()-1ではなく、len()としている
検索条件
binary_search()は「値そのものを探す」検索。
そのためleft==rightの時にも値を確認する必要がある。
→よって、while left<=rightという条件式に= が含まれている。
一方、lower_bound(), upper_bound()は
「条件を満たす境界の位置を探す検索」。
値との一致を直接チェックする必要はない。
→このためループの実行条件はleft < rightとし、
left = rightとなった時点で候補が尽きた状態＝答えが見つかった状態と判断できる。
つまり、
binary_searchは「一致する値があるかどうか」が重要。<=が必要。
lower_bound(), upper_bound()は「値が入るべき位置」が重要。==の比較は必要なく、<のみでOK。
left, rightの寄せる条件と方法
1: Lower
x <= arr[mid] のときは、
最初にx以上の値が出るidxを探す目的に対して、
arr[mid]がxを含む可能性があるので、rightをmidまで寄せる。
→right = mid
# 例：
arr = [1, 2, 2, 2, 3, 4]
x = 2
# arr[mid] = 2 のとき、その位置は2以上なので「条件に合ってる」→残す（right = mid）
2: Upper
arr[mid] <= xのときは、
xより大きい最初の値のあるidxを探す目的に対して、arr[mid]は条件を満たさないので取得範囲を狭めたい。
→midをスキップして、left = mid+1とする
# 例：
arr = [1, 2, 2, 2, 3, 4]
x = 2
# arr[mid] = 2 のとき、その位置は「x以下」なので対象外 → 左を寄せる（left = mid + 1）
感想：
計算アルゴリズムとして優秀だとされる二分探索をとりあえず描けるようになったのはでかい！
こういう基礎を引き続き勉強していきたい