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