bisect.bisect関数

ソート済みのシーケンス(リストなど)にソート順序を保ったまま要素を追加したい時、何番目の要素に追加すればよいかを返す。

(例)

>>> import bisect
>>> nums = [1, 3, 4, 9, 11, 17]
>>> bisect.bisect(nums, 5) # 5を追加するときのインデックスは?
3
>>> nums.insert(3, 5) # 5を3番目の要素として追加する
>>> nums
[1, 3, 4, 5, 9, 11, 17]

追加する要素と同じ値の要素が存在する時は、最後の要素の次の位置を返す。

>>> x = [1, 2, 3, 3, 3, 5, 6]
>>> bisect.bisect(x, 3)
5

同じ値の要素が連続する最初の位置を返す場合は、bisect_left関数を使う。

>>> x = [1, 2, 3, 3, 3, 5, 6]
>>> bisect.bisect_left(x, 3)
2

参考文献

Fluent Python P.47〜P.48