Python bisectモジュール入門：二分探索でリストを常にソート済みに保つ方法

長いリストに対して、要素を挿入するたびにソート処理を実行すると、プロセッサへの負荷が大きく、時間もかかってしまいます。Pythonのbisectモジュールを使えば、二分探索（バイセクション）アルゴリズムによって、要素を挿入した後もリストが自動的にソートされた状態を維持できます。このモジュールには、主に以下の関数が用意されています。

bisect_left()

指定した要素を挿入すべき位置（挿入ポイント）を、リストのソート順序を維持できるように検索します。同じ値の要素がすでにリスト内に存在する場合は、その既存要素の左側（手前）が挿入ポイントとして返されます。戻り値は list.insert() の第1引数としてそのまま利用できます。

bisect_right()

動作は bisect_left() とほぼ同じですが、同じ値の既存要素が存在する場合、その右側（後ろ）になる挿入ポイントを返します。なお、bisect_right() はエイリアスとして単に bisect という名前でも呼び出せます。

insort_left()

指定した値を、ソート順序を崩さずにリスト a へ挿入します。これは a.insert(bisect.bisect_left(a, x, lo, hi), x) と同等の処理です。

insort_right() / insort()

どちらも insort_left() と同様の動作をしますが、同じ値の既存要素がリスト内にある場合は、その右側（後ろ）に新しい値を挿入します。

使用例

以下の例では、まず通常の sort() メソッドでリストを昇順に並べ替え、その後 bisect モジュールを使って適切な位置へ要素を挿入しています。

>>> nums = [45,21,34,87,56,12,5,98,30,63]
>>> nums.sort()
>>> nums
[5, 12, 21, 30, 34, 45, 56, 63, 87, 98]
>>> import bisect
>>> p = bisect.bisect_left(nums,50)
>>> p
6
>>> nums.insert(p,50)
>>> nums
[5, 12, 21, 30, 34, 45, 50, 56, 63, 87, 98]
>>> bisect.insort(nums, 29)
>>> nums
[5, 12, 21, 29, 30, 34, 45, 50, 56, 63, 87, 98]

この例では、bisect_left(nums, 50) が挿入位置「6」を返し、そこに 50 を挿入してもリストのソート順序は保たれています。さらに insort() を使えば、挿入位置の検索と挿入を1ステップで行えます。

パフォーマンスのメリット

bisectモジュールの関数は、挿入位置を O(log n) の計算量で高速に見つけられます。毎回全要素を並べ替える O(n log n) のソートと比べて効率が良いため、大量のデータを扱う場面や、頻繁に要素を追加しながらソート済み状態を維持したい場面で特に有効です。