Jason Pan

二分搜索解题要点

潘忠显 / 2021-05-27


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

看完之后,可以用 LeetCode 上 3435278704981 这五个题目练练手哦。

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

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

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

[1, 3, 5, 6]

共有5个可能的位置:

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

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

[0, nums.size() + 1)

这里(-1, 4]也行,如果能用自然数(uintsize_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

总结

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

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