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

bisect

• 前言
• 源码
• 对比
• 补充

前言

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

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

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

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

源码

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

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 ina[i:] have e >= x.  So if x already appears in the list, a.insert(i, x) willinsert just before the leftmost x already there.Optional args lo (default 0) and hi (default len(a)) bound theslice 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) // 2if a[mid] < x:lo = mid + 1else:hi = midelse:while lo < hi:mid = (lo + hi) // 2if key(a[mid]) < x:lo = mid + 1else:hi = midreturn lo

忽略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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！