Jason Pan

二分搜索解题要点

黄杰 / 2021-05-27

刷题的同学，如果很简单的二分搜索问题，还需要考虑半天，你就应该来了解一下 4 个解决二分搜索的要点了。

看完之后，可以用 LeetCode 上 34、35、278、704、981 这五个题目练练手哦。

要点1：使用半闭半开的搜索区间

使用左闭右开的搜索区间，有几个好处：

以35题为例解释，要找到数字位置或者可以插入的位置：

[1, 3, 5, 6]

共有5个可能的位置：

[ 1, 3, 5, 6, ]
 ↑  ↑  ↑  ↑  ↑
 0  1  2  3  4

找一个半开半闭的区间，将坐标范围框起来：

[0, nums.size() + 1)

这里(-1, 4]也行，如果能用自然数（uint 或 size_t）表示，就尽量用自然数。然后就可以进行二分搜索了

left = 0
right = 5
mid = (left + right) / 2

while left < right:  
  if xx:
    right = mid
  else:
    left = mid + 1
  mid = (left + right) / 2

return mid

仔细考虑一下：

while 条件一定能够终止：

**这种半开半闭的搜索方法基本上适用于绝大部分二分搜索的场景。**再考虑34题，找到一个数字的最先出现和最后出现的位置，可以拆分成两次 O(log n) 的搜索。

[5, 7, 7, 8, 8, 10]

我们先来分析下标的取值范围：

[5, 7, 7, 8, 8, 10]
 ↑  ↑  ↑  ↑  ↑  ↑
 0  1  2  3  4  5

两种情况下范围都是从0 到 len(nums) - 1，接下来，我们看看使用左闭右开区间（[0, len(nums))）处理是否合适。

搜索最左边的元素，mid的满足条件是：nums[mid] == target && (mid == 0 || nums[mid - 1] != target)

if nums[mid] > target:
    right = mid
elif nums[mid] < target:
    left = mid + 1
elif nums[mid] == target:
    if mid == 0 or nums[mid - 1]:
        return mid
    else:
        right = mid

上边代码很直观，当然也可以稍作重构，再加上while 条件：

left = 0
right = len(nums)
mid = (left + right) / 2
while left < right:
    if nums[mid] == target and (mid == 0 or nums[mid - 1]):
        return mid
    elif nums[mid] < target:
        left = mid + 1
    else:
        right = mid
    mid = (left + right) / 2
return -1

要点2：缩小搜索区间取决于场景

在 while 循环中，我们不断的缩小搜索范围，而如何缩小搜索区间的写法取决于场景。读者可以思考以下几种常见场景（均为升序序列）：

我们试着写一下缩小搜索范围的代码，暂时不考虑终止条件：

# 找到最先出现的一个 target
while some_condition:
  if nums[mid] == target:  # 1. mid 仍然在备选范围内，保留左半部分
      right = mid + 1
  elif nums[mid] < target: # 2. 大于和小于 target情形，mid 都不在备选范围内
      left = mid + 1
  else:
      right = mid
  mid = (left + right) / 2

# 找到最后出现的一个 target
while some_condition:
  if nums[mid] == target:  # 1. mid 仍然在备选范围内，保留右半部分
      left = mid
  elif nums[mid] < target: # 2. 大于和小于 target情形，mid 都不在备选范围内
      left = mid + 1
  else:
      right = mid
  mid = (left + right) / 2

# 找到一个存在的数
while some_condition:
    if nums[mid] == target:  # 1. 找到直接返回
        return mid
    elif nums[mid] > target: # 2. 取左半部分
        right = mid
    else:
        left = mid + 1      # 3. 取右半部分
assert(false)                # 4. 不可能走到这里

# 找到一个数的插入位置
while some_condition:
    if mid == nums.size():  # 1. 边界条件，最后一个位置
        return mid if target > nums[mid - 1] else mid - 1;   
    elif mid == 0 or nums[mid] == target or  # 2. 终止条件
        (nums[mid] > target && nums[mid - 1] < target):
        return mid
    elif nums[mid] > target:  # 3. 使用左半部分
        right = mid
    else:                     # 4. 使用右半部分
        left = mid + 1
assert(false)                 # 5. 不可能走到这里

要点3：利用 mid 判断终止，避免遍历不完整

因为是左闭右开，所以 left >= right 都不是一个合法的区间，是不是while left < right: 就可以了呢？

如果按照我们这种left, right, mid现在外边初始化一遍的话，while里边的mid应当写在left 和 right 更新之后，也就是while循环的最后边。这样如果 left == right 情况不被遍历到，那么最后一个 mid 将没有被用到，就漏掉了一次判断机会。

是不是将mid放在循环的最上边，就可以了呢？比如下边这样：

left = 0
right = len(nums)
while left < right:
    mid = (left + right) / 2
    if nums[mid] == target and (mid == 0 or nums[mid - 1]):
        return mid
    elif nums[mid] < target:
        left = mid + 1
    else:
        right = mid
return -1

答案是否定的，while循环的次数，由right和left决定，移动mid的位置，并没有影响right和left的产生过程。

那是不是循环条件改成 while left <= right: 就可以了呢？

left = 0
right = len(nums)
mid = (left + right) / 2
while left <= right:
    if nums[mid] == target and (mid == 0 or nums[mid - 1] < gggg):
        return mid
    elif nums[mid] < target:
        left = mid + 1
    else:
        right = mid
    mid = (left + right) / 2
return -1

答案也是否定的，当 left == right 的时候，假设满足最后一个条件，既 right = mid 的赋值会导致 left == right == mid 的情况，进而导致无限的循环下去。如果迭代区间的时候，如果有直接使用 mid 赋值的情形，一定不能 将left == right 作为循环条件的一部分。

我们再回过头去考虑第一种情况下 while left < right 漏掉的那种场景

但是**这种场景中，在本轮循环退出时，mid 是等于原来的 left，mid < right 的条件是成立的，**所以我们之前的所有条件都改成 while mid < right: 就包含了[mid, mid)的情况。

要点4：缩区间写法决定终止条件，利用[0, 1)判断是否会死循环

上边介绍了，可以使用 mid < right 作为循环条件，其实 left < mid 也可以作为循环条件，具体选用哪个，缩区间的写法。再考虑要点2中的几种场景，我们现在来补全循环条件：

# 找到最先出现的一个 target
while left < mid:          # 3. [0, 1) 场景下，第一个分支会进入 `mid < right` 的死循环，需要换做使用 `left < mid`
  if nums[mid] == target:  # 1. mid 仍然在备选范围内，保留左半部分
      right = mid + 1
  elif nums[mid] < target: # 2. 大于和小于 target情形，mid 都不在备选范围内
      left = mid + 1
  else:
      right = mid
  mid = (left + right) / 2

# 找到最后出现的一个 target
while left < mid:          # 3. [0, 1) 场景下，第一个分支会进入 `mid < right` 的死循环，需要换做使用 `left < mid`
  if nums[mid] == target:  # 1. mid 仍然在备选范围内，保留右半部分
      left = mid
  elif nums[mid] < target: # 2. 大于和小于 target情形，mid 都不在备选范围内
      left = mid + 1
  else:
      right = mid
  mid = (left + right) / 2

# 找到一个存在的数
while true:                  # 4. 区间绝对缩小，而且一定能返回
    if nums[mid] == target:  # 1. 找到直接返回
        return mid
    elif nums[mid] > target: # 2. 取左半部分
        right = mid
    else:
        left = mid + 1      # 3. 取右半部分
    mid = (left + right) / 2

总结

最后，还要提醒，不要犯低级错误，我个人容易犯的两个低级错误：

记住自己容易犯的错误，每次写完了再重点检查一下就好。