二分查找及其变形与Python的bisect模块的关系

首先，我们完成了二分查找及其变形的 3 个函数的模板：

1、binsearch(nums, target)：标准的二分查找，找不到返回-1；
2、lowerbound(nums, target)：查找第一个>=target的元素索引，找不到返回数组长度；
3、upperbound(nums, target)：查找第一个>target的元素索引，找不到返回数组长度。

class BinarySearch:

    # 标准的二分查找，找不到返回-1
    def binsearch(nums, target):
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                hi = mid - 1
            else:  # nums[mid] < target:
                lo = mid + 1
        return -1

    # 查找第一个>=target的元素索引，找不到返回数组长度
    def lowerbound(nums, target):
        lo, hi = 0, len(nums) - 1
        pos = len(nums)  # 找不到
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] >= target:
                hi = mid
            else:  # nums[mid] < target:
                lo = mid + 1
        if nums[lo] >= target: # lo就是要找的元素索引
            pos = lo
        return pos

    # 查找第一个>target的元素索引，找不到返回数组长度
    def upperbound(nums, target):
        lo, hi = 0, len(nums) - 1
        pos = len(nums)  # 找不到
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] > target:
                hi = mid
            else:  # nums[mid] <= target:
                lo = mid + 1
        if nums[lo] > target: # lo就是要找的元素索引
            pos = lo
        return pos

然后，我们介绍 Python 的 bisect 模块（import bisect）：

先说明的是，使用这个模块的函数前先确保操作的列表是已排序的。

• 有 3 个函数：bisect.bisect(list, val)、bisect.bisect_left(list, val)、bisect.bisect_right(list, val)，功能是在有序数组 list 中返回 val 插入位置的索引（不改变 list 本身），后两者适合包含重复元素的情况。实际上，bisect.bisect(list, val) 等价于 bisect.bisect_right(list, val)。

import bisect
a = [1,1,2,2,2,2,3,4,4,5,5,6,6,6]
print(bisect.bisect(a, 0))  # 1
print(bisect.bisect_left(a, 6))  # 11
print(bisect.bisect_right(a, 2))  # 6

• 有 3 个函数：bisect.insort(list, val)、bisect.insort_left(list, val)、bisect.insort_right(list, val)，功能是在有序数组 list 中插入 val （会改变 list 本身）。单纯看其结果的话，3 个函数的操作结果是一样的，其实插入的位置不同而已。

import bisect
a = [1,1,2,2,2,2,3,4,4,5,5,6,6,6]
bisect.bisect(a, 0)  # a = [0,1,1,2,2,2,2,3,4,4,5,5,6,6,6]
bisect.bisect_left(a, 6)  # a = [0,1,1,2,2,2,2,3,4,4,5,5,6,6,6,6]
bisect.bisect_right(a, 2)  # a = [0,1,1,2,2,2,2,2,3,4,4,5,5,6,6,6,6]

二分查找的变形与 bisect 模块的关系：

1、二分查找中的 lowerbound(nums, target) 函数等价于 bisect.bisect_left(list, val)；
2、二分查找中的 upperbound(nums, target) 函数等价于 bisect.bisect_right(list, val) 或 bisect.bisect(list, val)。