Pythonのbisectで2分探索

はじめに

この記事では、Pythonの標準ライブラリであるbisectを用いて、効率的に2分探索を行う方法について紹介します。

bisectライブラリの基本

bisectライブラリは、ソートされたリストに対して指定した値の挿入ポイントを2分探索によって見つけるために使用されます。以下のコード例は、その基本的な使い方を示しています。

import bisect

tmp = [2, 4, 6, 8]
index = bisect.bisect(tmp, 5)
print(index)  # 出力: 2

この例では、リスト [2, 4, 6, 8] の中で、値 5 を挿入するべき位置を返します。結果は 2 で、リストを [2, 4, 5, 6, 8] にすることができます。

bisect_left と bisect_right

bisect_left と bisect_right は、同じ値がリスト内に存在する場合に、その値の左側または右側のインデックスを返します。

tmp = [2, 4, 5, 6, 8]
left_index = bisect.bisect_left(tmp, 5)
right_index = bisect.bisect_right(tmp, 5)
print(left_index)  # 出力: 2
print(right_index)  # 出力: 3

insort メソッド

insort メソッドを使用すると、指定した値をリストの適切な位置に挿入することができます。

bisect.insort(tmp, 5)
print(tmp)  # 出力: [2, 4, 5, 5, 6, 8]

応用: 辞書やdataclassを扱う

bisectは辞書やdataclassを要素とするリストにも使用できます。この場合、key引数を使用して比較に用いるキーを指定します。

from dataclasses import dataclass

@dataclass
class TmpData:
    name: str
    age: int

tmp = [TmpData('tanaka', 20), TmpData('sato', 40)]
index = bisect.bisect(tmp, TmpData('', 30), key=lambda x: x.age)
print(index)  # 出力: 1