Pythonのbisectモジュール完全解説：二分挿入アルゴリズムでソート済みリストを効率的に操作する

Pythonには、bisectという標準モジュールが用意されています。このモジュールを使用すると、二分挿入（バイセクション）アルゴリズムを活用でき、ソート済みリストに対して「どこにデータを挿入すればリストがソートされた状態を保てるか」を高速に調べたり、実際に適切な位置へ要素を挿入したりすることができます。

二分探索をベースとしているため、線形探索のように先頭から順番に比較する必要がなく、大規模なデータでも非常に効率的に動作する点が大きな特徴です。

このモジュールを利用するには、まず以下のようにインポートします。

import bisect

bisectモジュールには、主に以下の6つの関数が用意されています。それぞれの役割を見ていきましょう。

bisect.bisect(list, element, begin, end)

ソート済みリストの中から、指定した要素を挿入してもリストの順序が崩れない位置を返します。引数には対象のリスト、挿入したい要素、そして検索範囲の開始インデックスと終了インデックスを指定できます（範囲は省略可能です）。もし同じ値の要素がすでにリスト内に存在する場合は、その中で最も右側（末尾寄り）の挿入位置を返します。

bisect.bisect_left(list, element, begin, end)

動作はbisect()メソッドとほぼ同じですが、同じ値がすでに存在する場合に、最も左側（先頭寄り）の挿入位置を返す点が異なります。重複要素のうち既存の要素より前に挿入したい場合に便利です。

bisect.bisect_right(list, element, begin, end)

このメソッドはbisect()メソッドと完全に同じ動作をします。つまり、重複する値が存在する場合は右側の挿入位置を返します。コードの意図を明確にしたい場合に、こちらの名前を使うこともあります。

bisect.insort(list, element, begin, end)

指定した要素を正しい位置に挿入し、リスト全体をソート済みの状態に保ったまま更新します。検索だけでなく実際の挿入まで行ってくれるのがbisect()との違いです。同じ値がすでに存在する場合は、右側の位置に挿入されます。

bisect.insort_left(list, element, begin, end)

insort()メソッドとほぼ同じですが、同じ値がすでに存在する場合に左側の位置に挿入される点が異なります。

bisect.insort_right(list, element, begin, end)

insort()メソッドと完全に同じ動作をします。右側への挿入であることを明示したい場合に使用します。

サンプルコード

それでは、実際にこれらの関数を使った例を見てみましょう。

import bisect
my_list = [11, 25, 36, 47, 56, 69, 69, 69, 78, 78, 91, 102, 120]
print('53を挿入する正しい位置: ' + str(bisect.bisect(my_list, 53, 0, len(my_list))))
print('69を挿入する右側の位置: ' + str(bisect.bisect_right(my_list, 69, 0, len(my_list))))
print('69を挿入する左側の位置: ' + str(bisect.bisect_left(my_list, 69, 0, len(my_list))))
bisect.insort(my_list, 59, 0, len(my_list))
print(my_list)
bisect.insort_left(my_list, 78, 0, len(my_list))
print(my_list)

実行結果

53を挿入する正しい位置: 4
69を挿入する右側の位置: 8
69を挿入する左側の位置: 5
[11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 91, 102, 120]
[11, 25, 36, 47, 56, 59, 69, 69, 69, 78, 78, 78, 91, 102, 120]

この実行結果から、次のことが読み取れます。

• 値53は47と56の間に収まるため、挿入位置はインデックス4になります。
• 値69はすでに3つ存在するため、bisect_right()では連続する69の右端（インデックス8）、bisect_left()では左端（インデックス5）がそれぞれ返されます。
• insort()を使うと、値59が自動的に正しい位置に挿入され、リストは常にソート済みの状態を保たれます。

このようにbisectモジュールを使いこなせば、ソート済みリストへの挿入処理をシンプルかつ高速に実装できます。優先度付きキューのようなデータ構造を自作する際や、時系列データの管理などにも幅広く活用できるので、ぜひ覚えておきましょう。