本片文章介紹一下python的bisect二分查找包，該包用于一個(gè)從小到大已經(jīng)排序的數(shù)組中，在想插入某個(gè)數(shù)時(shí)，還依然保持從小到大的排序規(guī)則。

背景

通過一個(gè)leetcode的題目(長(zhǎng)度最小的子數(shù)組)來介紹：

給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長(zhǎng)度最小的連續(xù)子數(shù)組，并返回其長(zhǎng)度。如果不存在符合條件的連續(xù)子數(shù)組，返回 0。

示例：
輸入：s = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長(zhǎng)度最小的連續(xù)子數(shù)組。 

進(jìn)階：
如果你已經(jīng)完成了 O(n) 時(shí)間復(fù)雜度的解法, 請(qǐng)嘗試 O(n log n) 時(shí)間復(fù)雜度的解法。

根據(jù)官方提供的前綴和與二分查找解法，可以很好的利用python的bisect包來進(jìn)行求解。

因?yàn)橐粋€(gè)正整數(shù)的數(shù)組 nums，如果將前i個(gè)數(shù)的和標(biāo)記為 numsSums[i] 的話，那么數(shù)組 numsSums 將是一個(gè)從小到大的數(shù)組，那么我們?cè)诓檎?nums 中，某個(gè)數(shù)作為子數(shù)組的第一個(gè)數(shù)組時(shí)，向右去查找最短連續(xù)子數(shù)組的問題，就變成了 numsSums 中某個(gè)數(shù)據(jù)的位置。

該題的具體解法：

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包包含的函數(shù)如下

['__builtins__', '__cached__', '__doc__', '__file__', '__loader__', '__name__', '__package__', '__spec__', 'bisect', 'bisect_left', 'bisect_right', 'insort', 'insort_left', 'insort_right']

其中

• bisect / bisect_left / bisect_right 是查找出在升序數(shù)組中插入某個(gè)數(shù)的下表位置（從0開始）；bisect_left / bisect_right 是針對(duì)數(shù)組中有重復(fù)數(shù)據(jù)的處理，bisect_left 表示插入到重復(fù)數(shù)據(jù)的左邊，bisect_right 表示插入到重復(fù)數(shù)據(jù)的右邊；并且在有重復(fù)數(shù)據(jù)的情況下，bisect / bisect_right 的執(zhí)行結(jié)果相同
• insort / insort_left / insort_right 是直接在原有數(shù)組中執(zhí)行插入操作，插入的原則是上述 bisect / bisect_left / bisect_right 的規(guī)則

例子如下：

>>> 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]

總結(jié)

bisect 包只能使用在升序排序的數(shù)組中，如果想要在逆序的數(shù)組中進(jìn)行插入的話，得需要自己手動(dòng)寫二分查找了，例如如下：

# 左插入
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}')