本記事ではPythonで二分探索する方法を解説します。具体的にはPythonの標準モジュールである二分探索機能を提供するbisectの使い方を説明します。二分探索を使うことで大量のデータからの検索が劇的に速くなり、プログラムのパフォーマンスを向上させることができます。
二分探索とは
二分探索とは、ソート済みの配列やリストから特定の値を効率的に探すアルゴリズムです。探索対象のデータを半分に分割しながら検索を進めるため、線形探索（リストを1つずつ調べる方法）よりも高速です。
二分探索の特徴
- 事前にデータがソートされている必要がある
- 時間計算量は O(log N)（データ数Nに対して対数的な時間で探索できる）
- リストの中央を基準に検索を繰り返す
bisectの使い方
bisectモジュールはソート済みのリストに対して効率的に要素の挿入位置を見つけたり、挿入したりするための関数を提供します。内部的には二分探索を使用しているため、線形探索よりも高速に処理が可能です。
bisectモジュールには、主に以下の4つの関数が含まれています。
bisect_left関数
ソート済みリスト内で値が最初に現れる位置（左側の挿入位置）を見つけます。
構文
bisect.bisect_left(a, x, lo=0, hi=None, key=None)引数
a: ソート済みのリストx: 検索する値lo: 検索範囲の開始インデックス（デフォルトは0）hi: 検索範囲の終了インデックス（デフォルトはNone、リストの終端まで）key: （Python 3.10以降）各要素を比較するための関数（デフォルトはNone）
戻り値
xを挿入できる最も左側（最小のインデックス）の位置を返します。既にリスト内にxと等しい値がある場合は、その値の最初の位置を返します。
使用例
import bisect
sorted_list = [1, 2, 4, 4, 5, 7]
pos_left = bisect.bisect_left(sorted_list, 4)
print(pos_left) # 出力: 2bisect_right関数（bisect関数）
ソート済みリスト内で値が最後に現れた位置の次（右側の挿入位置）を見つけます。bisect関数はbisect_rightのエイリアスです。
構文
bisect.bisect_right(a, x, lo=0, hi=None, key=None)
# または
bisect.bisect(a, x, lo=0, hi=None, key=None)引数
a: ソート済みのリストx: 検索する値lo: 検索範囲の開始インデックス（デフォルトは0）hi: 検索範囲の終了インデックス（デフォルトはNone、リストの終端まで）key: （Python 3.10以降）各要素を比較するための関数（デフォルトはNone）
戻り値
xを挿入できる最も右側（xより大きい値の最初の位置）を返します。リスト内のすべてのxの後の位置を返します。
使用例
import bisect
sorted_list = [1, 2, 4, 4, 5, 7]
pos_right = bisect.bisect_right(sorted_list, 4)
print(pos_right) # 出力: 4insort_left関数
ソート済みリストの適切な位置（左側）に値を挿入します。
構文
bisect.insort_left(a, x, lo=0, hi=None, key=None)引数
a: ソート済みのリスト（変更されます）x: 挿入する値lo: 挿入範囲の開始インデックス（デフォルトは0）hi: 挿入範囲の終了インデックス（デフォルトはNone、リストの終端まで）key: （Python 3.10以降）各要素を比較するための関数（デフォルトはNone）
戻り値
Noneを返します（リストaが直接変更されます）。
使用例
import bisect
sorted_list = [1, 2, 4, 4, 5, 7]
bisect.insort_left(sorted_list, 4)
print(sorted_list) # 出力: [1, 2, 4, 4, 4, 5, 7]insort_right関数
ソート済みリストの適切な位置（右側）に値を挿入します。
構文
bisect.insort_right(a, x, lo=0, hi=None, key=None)引数
a: ソート済みのリスト（変更されます）x: 挿入する値lo: 挿入範囲の開始インデックス（デフォルトは0）hi: 挿入範囲の終了インデックス（デフォルトはNone、リストの終端まで）key: （Python 3.10以降）各要素を比較するための関数（デフォルトはNone）
戻り値
Noneを返します（リストaが直接変更されます）。
使用例
import bisect
sorted_list = [1, 2, 4, 4, 5, 7]
bisect.insort_right(sorted_list, 4)
print(sorted_list) # 出力: [1, 2, 4, 4, 4, 5, 7]注意点
ソート済みリストが前提
- bisectモジュールはソート済みのリストに対してのみ正しく動作します
- 未ソートのリストに対して使用すると、予期しない動作をする可能性があります
挿入コスト
- bisectを用いた検索はO(log N)ですが、実際の挿入操作(insort_leftやinsort_right)はO(N)かかります
- 大量のデータを扱う場合は、別のデータ構造（例: collections.dequeやsortedcontainers）を検討するべきです
keyパラメータの活用（Python 3.10以降）
Python 3.10から導入されたkeyパラメータを使用すると、複雑なデータ構造での比較がより簡単になります。keyパラメータには比較対象の要素から比較用の値を取り出す関数を指定します。
keyパラメータの使用例
以下の例では、タプルのリストを扱う場合にタプルの最初の要素（身長）を基準に二分探索を行います。
import bisect
# 身長（cm）と名前のタプルのリスト（身長順にソート済み）
people = [(160, "Alice"), (165, "Bob"), (170, "Charlie"), (175, "David")]
# key パラメータを使用して、身長を基準に検索
height_to_find = 168
index = bisect.bisect_left(people, height_to_find, key=lambda x: x[0])
print(f"挿入位置: {index}") # 出力: 2 (身長168はBob(165)とCharlie(170)の間)
# リストに身長 168 の新しい人を挿入
new_person = (168, "Eve")
people.insert(index, new_person)
print(people)
# 出力: [(160, 'Alice'), (165, 'Bob'), (168, 'Eve'), (170, 'Charlie'), (175, 'David')]まとめ
bisectモジュールは、ソートされたリストに対して二分探索を行い、要素の挿入や検索位置の特定を効率的に行うための機能を提供します。
主な関数は以下のとおりです。
bisect_left(a, x): xを左側（最も前）の位置に挿入できるインデックスを取得bisect_right(a, x): xを右側（最も後）の位置に挿入できるインデックスを取得insort_left(a, x): リストaにxを左側に挿入insort_right(a, x): リストaにxを右側に挿入
挿入そのものはリストの性質上O(N)となるため、大規模なデータや大量の挿入がある場合はデータ構造やアルゴリズムの選択を再考する必要があります。
ソートされたリストへの挿入が必要な場面では便利なモジュールなので、ぜひ活用してみてください。
