Pythonにおけるbisectの使い方説明

Pythonにおけるbisectの使い方説明
bisectはpython内蔵モジュールで、シーケンスの挿入と検索に使用されます.

検索:

bisect(array, item)

bisect_left(array, item)

bisect_right(array, item)

挿入:

insort(array,item)

insort_left(array,item)

insort_right(array,item)

1.検索

import bisect
arr = [1,3,3,6,8,12,15]
value = 3
idx_left=bisect.bisect_left(arr,value)
print(idx_left)
idx_right=bisect.bisect_right(arr,value)
print(idx_right)
#         insert    
arr.insert(idx_left,value)
print(arr)

出力:
1
3
1,3,3,3,6,8,12,15
**NOTE:**leftとleftを持たない用法の違いは、挿入された要素とシーケンス内の要素が同じである場合、その要素の前(左、left)に挿入されるか、後ろ(右)に挿入されるか、検索される場合、その要素の位置がその要素の後の位置に戻るかである.
2.挿入
bisectを使用insort、bisectより先にどの位置を挿入するかを探して、更にinsert方法で挿入するのがもっと速い方法

import bisect
 
a = [1,4,6,8,12,15,20]
bisect.insort(a,13)
print(a)

[1,4,6,8,12,13,15,20]
3.使用例
Leetcode-315問題の解決策

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        n=len(nums)
        result=[0]*n
        sorted_nums=[]
        for i in range(n-1,-1,-1):
            idx = bisect.bisect_left(sorted_nums,nums[i])
            sorted_nums.insert(idx,nums[i])
            result[i] = idx
        return result