bisect是python的内置模块, 用于有序序列的插入和查找。 插入的数据不会影响列表的排序, 但是原有列表需要是有序的, 并且不能是倒序.
Bisect模块提供的函数有:
在有序数组a中[lo,hi]区间内查找x插入的位置,返回的是索引值。如果a中有跟x相同的元素,则x插入的位置是左边,key指定了一个单参数的方法,该方法的返回值作为与k比较的基准。
值得注意的是,key参数是3.10版本以后才添加的功能
# bisect_left Vs. bisect (bisect_right) import bisect nums = [1, 2, 2, 4] i, j = bisect.bisect_left(nums, 2), bisect.bisect(nums, 2) print(i) # 输出1 print(j) # 输出3
可见,针对上面给出的数组,想要插入2,使用bisect_left返回的索引值是1,使用bisect(bisect_right)返回的索引值是3。如果指定了lo和hi的话,那么返回的就是在这个范围内的索引。如下面的例子所示。
# 指定lo和hi import bisect nums = [1, 2, 2, 2, 2, 4] i = bisect.bisect_left(nums, 2, 3) print(i) # 输出为3
如果不指定lo=3的话,返回的索引应该是1。指定lo=3后,返回的索引为3。
关键字key指定了一个方法,这个方法会接受当前数组中的中间值mid(因为二分查找就是从中间值开始的)作为其参数,然后返回一个值val,val用于跟x比较。
# 指定key值 import bisect nums = [1, 2, 3, 4, 6, 8] def divide(mid): print('mid: ' + str(mid)) return mid // 2 i = bisect.bisect_left(nums, 5, key=divide) print(i)
上面的例子中定义了一个divide方法。那么bisect_left方法的执行顺序是这样的:
# bisect.insort_left import bisect nums = [1, 2, 3, 4, 6, 8] bisect.insort_left(nums, 5) print(nums) # [1, 2, 3, 4, 5, 6, 8]
值得注意的是,insort方法中的key和bisect方法中的key指定的方法针对的对象是不同的。
# bisect.insort_left with key import bisect nums = [1, 2, 3, 4, 6, 8] def divide(mid): print('mid: ' + str(mid)) return mid // 2 bisect.insort_left(nums, 5, key=divide)
可见,key指定的方法的参数是针对x的。也就是说insort_left方法的执行顺序是这样的:
class BinarySearch: # 标准的二分查找,找不到返回-1 def binsearch(self, 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
class BinarySearch: # 查找第一个>=target的元素索引,找不到返回数组长度 def lowerbound(self, 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
class BinarySearch: # 查找第一个>target的元素索引,找不到返回数组长度 def upperbound(self, 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
lowerbound(nums, target)
等价于 bisect.bisect_left(a,x, lo=0, hi=len(a))
upperbound(nums, target)
等价于 bisect.bisect_right(a,x, lo=0, hi=len(a))
或者bisect.bisect(a,x, lo=0, hi=len(a))