本片文章介绍一下python的bisect二分查找包，该包用于一个从小到大已经排序的数组中，在想插入某个数时，还依然保持从小到大的排序规则。
背景
通过一个leetcode的题目(长度最小的子数组)来介绍：
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶：
如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
根据官方提供的前缀和与二分查找解法，可以很好的利用python的bisect包来进行求解。
因为一个正整数的数组 nums，如果将前i个数的和标记为 numsSums[i] 的话，那么数组 numsSums 将是一个从小到大的数组，那么我们在查找 nums 中，某个数作为子数组的第一个数组时，向右去查找最短连续子数组的问题，就变成了 numsSums 中某个数据的位置。
该题的具体解法：
import bisect
from typing import List
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
if not nums: return 0
numsLen = len(nums)
ans = numsLen + 1
numsSums = [0]
for item in nums:
numsSums.append(numsSums[-1], item)
for i in range(1, numsLen + 1):
target = numsSums[i - 1] + s
bisectIdx = bisect.bisect_left(numsSums, target)
if bisectIdx != numsLen + 1:
ans = min(ans, bisectIdx - i + 1)
return 0 if ans == numsLen + 1 else ans
详解bisect包
bisect包包含的函数如下
['__builtins__', '__cached__', '__doc__', '__file__', '__loader__', '__name__', '__package__', '__spec__', 'bisect', 'bisect_left', 'bisect_right', 'insort', 'insort_left', 'insort_right']
其中
-
bisect/bisect_left/bisect_right是查找出在升序数组中插入某个数的下表位置（从0开始）；bisect_left/bisect_right是针对数组中有重复数据的处理，bisect_left表示插入到重复数据的左边，bisect_right表示插入到重复数据的右边；并且在有重复数据的情况下，bisect/bisect_right的执行结果相同 -
insort/insort_left/insort_right是直接在原有数组中执行插入操作，插入的原则是上述bisect/bisect_left/bisect_right的规则
例子如下：
>>> a = [0, 1, 2, 3, 3, 3, 4, 5, 6]
>>> bisect.bisect(a, 2)
3
>>> bisect.bisect_left(a, 2)
2
>>> bisect.bisect_right(a, 2)
3
>>> bisect.bisect(a, 3)
6
>>> bisect.bisect_left(a, 3)
3
>>> bisect.bisect_right(a, 3)
6
>>> bisect.insort(a, 3)
>>> a
[0, 1, 2, 3, 3, 3, 3, 4, 5, 6]
>>> a.reverse()
>>> a
[6, 5, 4, 3, 3, 3, 3, 2, 1, 0]
>>> bisect.insort(a, 3)
>>> a
[6, 5, 4, 3, 3, 3, 3, 2, 1, 0, 3]
总结
bisect 包只能使用在升序排序的数组中，如果想要在逆序的数组中进行插入的话，得需要自己手动写二分查找了，例如如下：
# 左插入
nums = [6, 5, 4, 3, 3, 3, 3, 2, 1, 0]
low, high = 0, len(nums) - 1
target = 3
while low < high:
middle = (low + high) // 2
if target >= nums[middle]:
high = middle
else:
low = middle + 1
print(f'{target} left insert {nums} index is {low}')
