9.3 二分法アルゴリズムを利用する — bisect

Pythonの bisect モジュールは、すでにソートされている（並び替えられている）リストに対して、順序を保ったまま新しい要素を挿入したり、挿入すべき位置を検索したりするためのモジュールです。

内部で二分探索（バイナリサーチ）アルゴリズムを使用しているため、リストの要素数がどれだけ増えても、非常に高速に処理を行えるのが最大の特徴です。

本記事では、「9.3 二分法アルゴリズムを利用する」として、bisect モジュールの基本と実践的な使い方を解説します。

1. なぜ bisect が必要なのか？（二分探索の力）

通常、リストの中に新しい要素を正しい順序で挿入しようとすると、先頭から順番に大きさを比較していく必要があります（線形探索）。この方法だと、データが100万件あれば最悪100万回の比較が必要です。

しかし、データが「すでにソートされている」という前提があれば、二分探索が使えます。真ん中のデータと比較し、探している値がそれより小さければ左半分、大きければ右半分……と探索範囲を半分ずつに絞り込んでいく手法です。

これを使えば、100万件のデータでもわずか20回程度の比較で目的の位置を見つけることができ、処理速度が劇的に向上します。

2. 挿入箇所のインデックスを取得する：bisect()

要素をリストに追加する前に、「もし追加するとしたら、どのインデックス（位置）になるか」を調べる関数です。リスト自体は書き換えません。

• bisect.bisect(a, x): リスト a の中で、値 x が入るべきインデックスを返します。
• bisect.bisect_right(a, x): bisect() と全く同じ働きをします。もし同じ値が存在した場合は、**その値の右側（後ろ）**のインデックスを返します。
• bisect.bisect_left(a, x): もし同じ値が存在した場合は、**その値の左側（前）**のインデックスを返します。

import bisect

# 必ずソート済みのリストを用意する
data = [10, 20, 20, 20, 30, 40]

# 25 が入るべき位置（インデックス）を探す
index = bisect.bisect(data, 25)
print(index)  # 出力: 4

# 同じ値（20）が存在する場合の違い
print(bisect.bisect_right(data, 20)) # 出力: 4 (20のグループの右端)
print(bisect.bisect_left(data, 20))  # 出力: 1 (20のグループの左端)

3. リストに要素を挿入する：insort()

インデックスを調べるだけでなく、実際にリストへ要素を挿入する関数です。内部的には bisect で位置を探し、リストの insert() メソッドを呼び出しています。

• bisect.insort(a, x): リスト a に値 x を挿入します。
• bisect.insort_right(a, x): insort() と同じ働きです（同じ値があれば右側に挿入）。
• bisect.insort_left(a, x): 同じ値があれば左側に挿入します。

import bisect

numbers = [10, 20, 30, 40]

# 25を適切な位置に挿入
bisect.insort(numbers, 25)
print(numbers)
# 出力: [10, 20, 25, 30, 40] (ソート順が保たれている)

4. 実用的な活用テクニック：点数によるランク付け

bisect モジュールの公式ドキュメントでも紹介されている、非常に実用的なテクニックです。 ある点数がどのランク（A, B, C, Dなど）に該当するかを、大量の if-elif 文を書かずに判定できます。

import bisect

def get_grade(score):
    # 区切りの境界値（ソート済みであること）
    breakpoints = [60, 70, 80, 90]
    # 対応するランク（インデックスと連動させる）
    grades = ['F', 'D', 'C', 'B', 'A']

    # score が breakpoints のどの位置に入るかを取得し、
    # そのインデックスを使って grades からランクを取り出す
    index = bisect.bisect(breakpoints, score)
    return grades[index]

# テスト
scores = [33, 99, 77, 70, 89, 90, 100]
results = [get_grade(score) for score in scores]

print(results)
# 出力: ['F', 'A', 'C', 'C', 'B', 'A', 'A']

このように、境界値のリストに対して bisect() を実行するだけで、複雑な条件分岐をシンプルかつ高速に処理することができます。