二分搜索

在计算机科学中，二进制搜索，也被称为折半搜索算法，是一种搜索算法，每次搜索都能排除掉一半的不存在目标结果的集合，所以在最坏情况下，经过$log(n)$次搜索，得到最终结果。

解题实例

如何将二分搜索以代码的形式，转化为解决某几类问题的利器呢？下面以两种类型的题目为例，总结出一种通用的解题思路。

1.搜索某个值

搜索插入位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right:  # 搜索区间为[left, right]
            mid = left + (right - left) // 2
            val = nums[mid]
            if val == target:  # 找到目标值
                return mid
            elif val > target:
                right = mid - 1  # 目标值在mid左侧，更新搜索区间为[left, mid - 1]
            else:
                left = mid + 1  # 目标值在mid右侧，更新搜索区间为[mid + 1, right]
        # 当left=right时，mid=left=right
        # 如果val > target, target应该插入到mid前面(target下标为mid)，接着right=mid-1,left=mid跳出循环，结果为left
        # 如果val < target, target应该插入到mid后面(target下标为mid+1)，接着left=mid+1,right=mid跳出循环，结果为left
        # 所以最终返回都是left
        return left

2.求左（右）边界值

第一个错误的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:

        left = 1
        right = n
        while left <= right:  # 搜索区间[left, right]
            mid = left + (right - left) // 2
            if isBadVersion(mid):  # 是错误版本，则新区间为[left, mid-1]
                right = mid - 1
            else:  # 不是错误版本，则新区间为[mid+1, right]
                left = mid + 1
        return left

思路总结

可以看出，二分搜索是可以总结出固定的解题思路，快速写出解题代码。

  1. 确定搜索区间为$[left, right]$，注意是两边都闭的区间（当然也可以是$[left, right)$的区间，不过此时区间的初始值会不同，这个可以自己去想一想）

  2. 缩小区间

    • $mid$在所求值左边，下一搜索区间为$[left, mid-1]$
    • $mid$在所求值右边，下一搜素区间为$[mid+1, right]$
    • $mid$等于所求值，
      • 求确定值则直接返回$mid$
      • 求左边界，则归属为第一种情况
      • 求右边界，则归属为第二种情况

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

while left <= right:  # 固定用<=两端都闭区间，避免开左闭右开不易记忆
    mid = left + (right - left) // 2  # 不用(left+right)//2，可以避免溢出
    # 根据条件决定区间如何缩小
    # left往右移，则left=mid+1
    # right往左移，则right=mid-1
    # 根据具体题意来定
    if mid == target:
        # do_something
    elif mid > target:
        # do_something
    else:
        # do_something
# 最后一次循环，left=right=mid，三个值相等
# left右移，left加1,
#   最终mid=right=left-1
# right左移，right减1
#   最终mid=left=right+1