bisect ライブラリについて紹介する。あまり使用頻度が高くないので、備忘録として記録する。
bisect
bisect は指定した値を配列から 2 分探索する。以下のようなイメージである。
探索したい値：5
探索対象の配列：[2, 4, 6, 8]
>>> import bisect
>>> tmp = [2,4,6,8]
>>> bisect.bisect(tmp,5)
2
返り値は、配列に対して挿入する index 番号である。
[2, 4, 5, 6, 8]
3 番目に挿入するので、返り値は「2」となる。
引数は以下の通り(Python 3.10.x)。第 3 引数以降は任意の引数である。
bisect.bisect(配列, 探索する値, 探索開始位置, 探索終了位置, key)
注意点としては配列はしっかりソートされてあることが前提で使用される。
配列の一部分を使用する場合は、第 3 引数、第 4 引数を指定するよい。
配列の要素が辞書や dataclass の場合は、key に key 関数を指定する。
>>> @dataclass
... class tmpdata:
... name: str
... age: int
...
>>> tmp = []
>>> tmp.append(tmpdata('tanaka', 20))
>>> tmp.append(tmpdata('sato', 40))
>>> tmp
[tmpdata(name='tanaka', age=20), tmpdata(name='sato', age=40)]
>>> bisect.bisect(tmp, 30, key=lambda self: self.age)
1
bisect_left, bisect_right
bisect_left, bisect_right は探索する値と等しい値がある場合を右/左の index 番号を返す。
探索したい値：5
探索対象の配列：[2, 4, 5, 6, 8]
>>> tmp = [2,4,5,6,8]
>>> bisect.bisect_left(tmp, 5)
2
>>> bisect.bisect_right(tmp, 5)
3
insort(_left/right)
探索した index へ挿入したい場合は、insort メソッドを使用する。
探索したい値：5
探索対象の配列：[2, 4, 5, 6, 8]
>>> bisect.insort_left(tmp,5)
>>> tmp
[2, 4, 5, 5, 6, 8]
Python 学習本
https://amzn.to/3TPP9Is