Python二分查找 - bisect
2022年10月2日
二分查找模块 bisect
bisect_left(a, x, lo=0, hi=len(a))
相当于 left_bound，返回目标值的左侧边界，其返回值的解读：
- 解读 1：将 x 插入有序数组 a 中的最左侧索引
- 解读 2：a 中小于 x 的值的数量
- 解读 3：有序数组 a 中大于等于 x 的最小元素索引
bisect_right(a, x, lo=0, hi=len(a))
bisect(a, x, lo=0, hi=len(a))
⚠️ 不相当于 right_bound，返回目标值的右侧边界+1，其返回值的解读：
- 解读 1：将 x 插入有序数组 a 中的最右侧索引
- 解读 2：a 中小于等于 x 的值的数量
- 解读 3：有序数组 a 中大于 x 的最小元素索引（返回的索引位置的值肯定不等于 x！！！
insort_left(a, x, lo=0, hi=len(a))
等价于 a.insert(bisect.bisect_left(a, x, lo, hi), x)
insort_right(a, x, lo=0, hi=len(a))insort(a, x, lo=0, hi=len(a))
等价于 a.insert(bisect.bisect_right(a, x, lo, hi), x)
#idx 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
a = [0, 1, 2, 3, 3, 3, 3, 3, 5, 8]
>>> bisect_left(a, 3)
3
>>> bisect_right(a, 3) # bisect(a, 3)
8
>>> bisect_left(a, 4)
8
>>> bisect_right(a, 4)
8
python3.10 之后的版本新增参数 key
类似 sort 的 key 参数，可以指定搜索时使用的具体的键
例子：
# leetcode #875
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
def canEatAll(k):
if k == 0:
return False
cost_time = 0
for pile in piles:
cost_time += math.ceil(pile / k)
return cost_time <= h
return bisect_left(range(max(piles) + 1), True, key=canEatAll)
注意
若使用这种方法解题，a 要包括所有的答案域，且如果使用 range，尽量使用 range(max_ans+1)的形式，若使用 range(min_ans, max_ans+1)，需要给返回的结果添加偏置 min_ans！
在有序列表中搜索
如何将 bisect 转换为一般的搜索方法：
def index(a, x):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
def find_lt(a, x):
'Find rightmost value less than x'
i = bisect_left(a, x)
if i:
return a[i-1]
raise ValueError
def find_le(a, x):
'Find rightmost value less than or equal to x'
i = bisect_right(a, x)
if i:
return a[i-1]
raise ValueError
def find_gt(a, x):
'Find leftmost value greater than x'
i = bisect_right(a, x)
if i != len(a):
return a[i]
raise ValueError
def find_ge(a, x):
'Find leftmost item greater than or equal to x'
i = bisect_left(a, x)
if i != len(a):
return a[i]
raise ValueError