Python二分查找的左闭右闭和左闭右开

前言

话说刷题刷到一个简单二分查找的题，根据我的肌肉记忆马上写出了下面的代码也AC了

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)-1
        while l <= r:
            mid = (l+r)//2
            if nums[mid] >= target:
                r = mid-1
            else:
                l = mid+1
        return l
1
2
3
4
5
6
7
8
9
10

然后想到有标准库好像可以直接用

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect.bisect_left(nums, target)
1
2
3

源码

于是哥们就来看看源码，优化一下，发现了不对劲。

def bisect_left(a, x, lo=0, hi=None, *, key=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(i, x) will
    insert just before the leftmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    # Note, the comparison uses "<" to match the
    # __lt__() logic in list.sort() and in heapq.
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

忽略key相关的部分，主要不同就在于hi也就是右边界的选择以及循环的判断和后续划分区间的操作。

对比

以我的猪脑一时间想不出来其中的关键点，去查资料。
在别人的文章找到了答案

二分法的写法共分两种分别是：1.定义target在左闭右闭区间 2.定义target在左闭右开区间。
方法1. 定义target在左闭右闭区间，即[left, right]
1.while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=。
2.if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle – 1。
方法2. 定义target在左闭右闭区间，即[left, right)
1.while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的。
2.if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]。

两种写法的左边界都是可以取到的，所以当mid不是寻找的值时就统一做l=mid+1；左闭右闭写法的右边界是可以取到的，于是做r=mid-1，而左闭右开写法的右边界取不到，于是做r=mid。
while循环的判断也是一样的道理。
感觉不到两种写法有什么性能上的差异，所以总结一下就是我的写法比较好记。

补充

https://stackoverflow.com/questions/35256433/binary-search-terminating-condition