Pythonのbisectモジュールを使った二分探索の実装方法

この記事では、Pythonのbisectモジュールについて詳しく解説します。bisectは二分探索（バイナリサーチ）を行うための標準ライブラリ関数で、ソート済みリストから要素を効率的に検索したい場合に非常に便利なツールです。

ここでは、bisectを使って実現できる3つの代表的なタスクを、具体的なサンプルコードとともに紹介します。

1. 要素の最初の出現位置を見つける

bisect.bisect_left(a, x, lo=0, hi=len(a)) は、ソート済みリスト a の中に x を挿入する場合の「最も左側の挿入位置」を返します。第3引数と第4引数は省略可能で、これらを指定するとリストの一部（部分区間）だけを対象に検索することもできます。

サンプルコード

from bisect import bisect_left
def BinSearch(a, x):
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return -1

a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(4)
pos = BinSearch(a, x)
if pos == -1:
    print(x, "is absent")
else:
    print("First occurrence of", x, "is at position", pos)

実行結果

First occurrence of 4 is at position 2

リスト内に重複した値が存在する場合でも、bisect_left を使えばそのうち最初（最も左）の出現位置を正確に特定できます。

2. xより小さい値の中で最大のものを見つける

bisect_left を応用すると、キー x より小さい値のうち最大のもの（直前の要素）を取得できます。これは「x未満の最大値」を求めたい場面で役立ちます。

サンプルコード

from bisect import bisect_left
def BinSearch(a, x):
    i = bisect_left(a, x)
    if i:
        return i-1
    else:
        return -1

a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(8)
pos = BinSearch(a, x)
if pos == -1:
    print(x, "is absent")
else:
    print("Larger value, smaller than", x, "is at position", pos)

実行結果

Larger value, smaller than 8 is at position 4

この例では、8より小さい値の中で最大の「5」（インデックス4）が返されています。i が0の場合は該当する要素が存在しないため、-1を返すようにしています。

3. 要素の最後の出現位置を見つける

bisect.bisect_right(a, x, lo=0, hi=len(a)) は、ソート済みリスト a の中に x を挿入する場合の「最も右側の挿入位置」を返します。こちらも最後の2つの引数は省略可能で、部分区間の検索に利用できます。

サンプルコード

from bisect import bisect_right
def BinSearch(a, x):
    i = bisect_right(a, x)
    if i != len(a) + 1 and a[i-1] == x:
        return i-1
    else:
        return -1

a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(36)
pos = BinSearch(a, x)
if pos == -1:
    print(x, "is absent")
else:
    print("Right most occurrence of", x, "is at position", pos)

実行結果

Right most occurrence of 36 is at position 9

リストには36が3つ含まれていますが、bisect_right を使うことで最後（最も右）の出現位置であるインデックス9を取得できました。

まとめ

bisectモジュールを活用すれば、ソート済みリストに対する二分探索を自分で実装することなく、シンプルかつ高速に行えます。特に以下の使い分けを覚えておくと便利です。

• bisect_left：最初の出現位置や挿入位置（左側）を調べたいとき
• bisect_right：最後の出現位置や挿入位置（右側）を調べたいとき

どちらの関数も計算量はO(log n)と効率的なので、大量のデータを扱う検索処理にも安心して使えます。