编写二分查找的正确姿势

一句话总结，写 bisection 而不是写 binary search。

Bisection

Bisection 定义

给定一个返回布尔值的函数 f ，在序列 a 中找到最小的索引 k ≥ 0 ，使得所有索引 i < k 有 f(a[i]) == false ，所有索引 j ≥ k 有 f(a[j]) == true 。(精确将数组分成了两半）

因为 bisection 的写法可以是固定的，手写二分时，先写出 bisection ，然后根据需求定义函数 f 找出自己想要的索引。

这样就只需要思考定义布尔函数，不再需要注意各种边界问题。大大减少了精神负担。

然后 bisection 的写法：

def bisect(arr, f):
    i, j = 0, len(arr)
    while i < j:
        mid = i + (j - i) // 2
        if not f(arr[mid]):
            i = mid + 1
        else:
            j = mid
    return i

解释：

1. 首先对数组 arr 的搜索范围固定是 [0:len(arr) - 1] 闭区间，和 i < j 条件对应，始终保持访问的是合法下标，但注意最后返回的是 i ，因为可能整个数组都没有满足条件的索引会导致 i = len(arr) 。

2. mid 需要防溢出（Python 这里就没必要了），同时保证 mid 永远不可能等于 j ，因为向下取整的除法，会让 j 和 i 相差 1 的时候偏向 i 。

3. 我们需要确保循环能够正确终止，在不满足 f 条件判断时，可以放心更新 i = mid + 1 以缩小搜索范围，同时 mid 的计算方式保证 j = mid 也是缩小搜索范围，确保每次循环都能将搜索范围减 1，最终 i == j 时循环终止。

应用举例

• 查找有序数组中是否存在 target:

  # 分成两半，一半 < target ，一半 >= target
  def binary_search(arr, target):
      k = bisect(arr, lambda x: x >= target)
      return k < len(arr) and arr[k] == target
  

• 查找有序数组中第一个大于 target 的索引：

  # 分成两半，一半 <= target，一半 > target
  def greater(nums, target):
      return bisect(nums, lambda x: x > target)
  

---

Loading Comments...