4 二分查找

  二分查找在 C++ 中有所谓的std::lower_bound和std::upper_bound可以实现。在 python 中也有对应的方法。

bisect 库提供的方法

  bisect是一个能在蓝桥杯赛场上使用的 python 库，其中主要提供两个函数：

• bisect.bisect_left：对标std::lower_bound，查找一个列表中第一个不小于某值的元素，返回其在列表中的索引。
• bisect.bisect_right：对标std::upper_bound，查找一个列表中第一个大于某值的元素，返回其在列表中的索引。

from bisect import bisect_left, bisect_right
a = [1,1,4,5]
print(bisect_left(a,1)) # 0
print(bisect_right(a,1)) # 2

方法的重要参数

定义查找区间

  bisect_left和bisect_right都有参数lo和hi，可以用于控制二分查找的区间，查找区间的索引将被限定在[lo,hi)。

from bisect import bisect_left, bisect_right
a = [1,1,4,5]
print(bisect_left(a,1,lo=1)) # 1
print(bisect_right(a,3,hi=1)) # 1

而在默认情况下，lo=0，hi=len(a)。虽然 python 列表支持负数索引，但最好还是不要给lo,hi传负数，可能会发生意想不到的事情。

定义查找方法

  key参数可以让我们自己定义一个比较逻辑，即不是在原来的列表中查找，而是在进行key变换之后的列表中进行查找。有了这个参数，bisect的功能就比较强大了，至少可以实现在降序列表中查找第一个不大于（或者小于）某值的元素。

from bisect import bisect_left, bisect_right
a = [9,8,7,7,6,0]
print(bisect_left(a,-7,key=lambda x:-x)) # 2
print(bisect_right(a,-7,key=lambda x:-x)) # 4

这里key只对列表起一个映射的作用，映射后的新列表是升序排序的。注意这里参数x=-7并不会被key进行映射。可能会想这样写：

a = [9,8,7,7,6,0]
print(bisect_left(a,7,key=lambda x:-x)) # 6, 即列表长度

意味着没找到大于等于 $7$ 的元素，所以返回列表长度。如果想避免错误，可以养成这样的习惯：

a = [9,8,7,7,6,0] # 待查找列表
x = 7 # 待查找元素
key = lambda x:-x # 查找方法
print(bisect_left(a,key(x),key=key)) # 2
print(bisect_right(a,key(x),key=key)) # 4