二分查找及其变形与Python的bisect模块的关系
二分查找及其变形与Python的bisect模块的关系
echobingo
发布于 2019-11-11 13:05:50
发布于 2019-11-11 13:05:50
首先，我们完成了二分查找及其变形的 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 删除
评论
登录后参与评论
推荐阅读
目录