[数据结构与算法]python实现bisect_left()和bisect_right()

原理

bis_left函数返回排序数组中值等于k的最左索引，如果没有，就返回插入后其索引
bis_right函数返回排序数组中值等于k的最右索引+1，如果没有，就返回插入后其索引

代码

因为二分查找的边界条件较为复杂，一般问题都可以用2种终止条件处理，我的理解是：
当终止条件为i>j的版本时，左右指针其中一个变为mid+1或者mid-1，另一个维持mid；
当终止条件为i==j的版本时，左右指针分别是mid+1和mid-1。

1. 终止条件为i>j的版本

def bis_left(nums, k):
    i, j = 0, len(nums)-1
    while i <= j:
        mid = i + ((j-i) >> 1)
        if nums[mid] >= k:
            j = mid-1
        else:
            i = mid+1
    return i

def bis_right(nums, k):
    i, j = 0, len(nums)-1
    while i <= j:
        mid = i + ((j-i) >> 1)
        if nums[mid] <= k:
            i = mid+1
        else:
            j = mid-1
    return i

2. 终止条件为i==j的版本，更贴近源码的逻辑

def bis_left(nums, k):
    i, j = 0, len(nums)
    while i < j:
        mid = i + ((j-i) >> 1)
        if nums[mid] >= k:
            j = mid
        else:
            i = mid+1
    return i

def bis_right(nums, k):
    i, j = 0, len(nums)
    while i < j:
        mid = i + ((j-i) >> 1)
        if nums[mid] <= k:
            i = mid+1
        else:
            j = mid
    return i

参考

Python3二分查找库函数bisect(), bisect_left()和bisect_right()介绍
Python bisect模块的使用方法及源码实现

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖