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

echobingo

发布于 2019-11-11 05:05:50

72600

代码可运行

文章被收录于专栏：Bingo的深度学习杂货店Bingo的深度学习杂货店

运行总次数：0

代码可运行

首先，我们完成了二分查找及其变形的 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)。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法