Python | Pythonの標準ライブラリで二分探索を簡単に使う方法（bisect モジュール）

要点

Python標準ライブラリの bisect モジュールを使うと、ソート済みリストに対して二分探索を簡単に実行できます。bisect_left や bisect_right を使えば、値を挿入すべき位置を高速に求められます。

bisect モジュールの基本

• 対象: ソート済みリスト（昇順が前提）
• 特徴: 内部で二分探索を行い、値を挿入すべき位置を返す
• 計算量: O(log n)（線形探索より高速）

主な関数

使用例

import bisect

a = [10, 20, 30, 40, 50]

# 挿入位置を調べる
pos = bisect.bisect_left(a, 35)
print(pos)  # 3 → 40の前に入る

# 実際に挿入する
bisect.insort_left(a, 35)
print(a)  # [10, 20, 30, 35, 40, 50]

import bisect

a = [10, 20, 30, 40, 50]

# 挿入位置を調べる
pos = bisect.bisect_left(a, 35)
print(pos)  # 3 → 40の前に入る

# 実際に挿入する
bisect.insort_left(a, 35)
print(a)  # [10, 20, 30, 35, 40, 50]

注意点

• リストは必ずソート済みであること（ソートされていないと正しい結果が得られない）
• 検索ではなく「挿入位置」を返すので、値が存在するかどうかを確認するには追加のチェックが必要
• Python 3.10以降では key パラメータを指定して、オブジェクトの特定属性を基準に探索可能

まとめ

• bisect は ソート済みリストの検索・挿入位置決定に便利。
• bisect_left / bisect_right で位置を求め、insort_left / insort_right で挿入できる。
• 大規模データでも高速に処理できるので、検索アルゴリズムやランキング処理に役立つ。