本片文章介绍一下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}')