二分查找算法的细节 Link to heading

初学者在写二分查找代码时，通常会遇到如下两个问题：

1. 使用闭区间、左闭右开区间、还是左开右闭区间呢？

2. 如何处理“等于”的逻辑，是收缩左侧还是收缩右侧？

对于第一个问题，其实就是在改变边界的时候究竟是使用 mid, mid + 1 还是 mid - 1 的问题，只要注意一个原则：本次迭代中 mid 已经被计算过了，要保证收缩后区间不包含 mid。例如使用左闭右闭区间，那么 L 永远更新为 mid - 1。

对于第二个问题，看了一下零茶山艾府的视频，感觉又有了更深的理解：

我们将查找分为四类：大于某值、大于等于某值、小于某值、小于等于某值

听起来不是很好理解，我们加上图片介绍：

对于一个二分搜索函数 bisect(nums, x) 来说，运行 bisect(nums, 5)，或许想找到以下结果：

1. 找到所有大于 5 的元素边界 i，以确保 nums[i] >= 5 恒成立。对应索引 2
2. 找到所有大于 5 的元素边界 i，以确保 nums[i] > 5 恒成立。对应索引 5
3. 找到所有小于 5 的元素边界 i，以确保 nums[i] < 5 恒成立。对应索引 1
4. 找到所有小于 5 的元素边界 i，以确保 nums[i] <= 5 恒成立。对应索引 4

这几种方式其实是可以相互转化的，假设我们查询的列表都是整数，那么我们把 2-4 种查询都转化成第一种：

1. bisect(nums, x)
2. bisect(nums, x + 1)，即找到所有大于 5 + 1 = 6 的元素边界 i，以确保 nums[i] >= 6 恒成立。
3. bisect(nums, x) - 1
4. bisect(nums, x + 1) - 1

通过这样的分类，所有不同种类、不同边界的搜索都可以对应到同一个函数上。

模板 Link to heading

看了一下 CPython 的 bisect.py 源码，感觉实现的比较优雅，拿来当做模板用。

基本函数 bisect 的签名为 def bisect(a, x, lo=0, hi=len(a), *, key=None) -> int。引申出两种插入 bisect_left 和 bisect_right，两者的区别是：当 a 中有相同的 x 时，返回的位置在相同元素的最左侧还是最右侧。

两者的唯一区别：bisect_left 遇到等号朝左缩；bisect_right 遇到等号朝右缩。

 1def bisect_left(a, x): # 这里省略了 lo, hi, key 等参数
 2  lo = 0
 3  hi = len(a) # 左闭右开
 4  while lo < hi:
 5    mid = (lo + hi) // 2
 6    if a[mid] < x: # 尽可能不向右侧缩小
 7      lo = mid + 1
 8    else:
 9      hi = mid
10  return lo
11
12def bisect_right(a, x):
13  lo = 0
14  hi = len(a)
15  while lo < hi:
16    mid = (lo + hi) // 2
17    if a[mid] > x: # 尽可能不像左侧缩小
18      hi = mid
19    else:
20      lo = mid + 1
21  return lo