二分查找

什么是二分查找

电视中播出过一个猜价格节目，主持人会先挑选一件商品，并告诉你这件商品的价格范围，例如 [1, 11)（左闭右开），你每一次猜测价格之后，主持人都会告诉你准确价格比你猜的要高还是低，你的任务是用最少的次数猜到准确价格。这个游戏有许多不同的策略，例如先猜一个预期的价格，再根据主持人的提示一点点接近。另一个策略是每次猜测查询区间的中间值，在 [1, 11) 的查询区间内，第一次猜 5 元，猜中了的话直接结束游戏，否则根据主持人的提示将查询区间更新为 [1, 5) 或者 [6, 11)，继续猜查询区间的中间值，相比第一种策略，这种方法每次都减少一半的查询区间，确保在最坏情况下也只需要 3 次就能猜中，更加稳定。这种每次减少一半查询区间的优化技巧就是二分查找的基本思想。

课前练习

尝试做以下几题，并且阅读官方题解：

• 69. x 的平方根
• 278. 第一个错误的版本
• 153. 寻找旋转排序数组中的最小值

什么时候使用二分查找

二分查找的题目通常有以下特点：

1. 返回结果是查询区间内符合要求的最小值或最大值

   • 猜价格节目中：找到最小的大于等于准确价格的数值
   • 69. x 的平方根 ：找到最小的整数 i，使 i^2 大于 x，返回结果是 i - 1
   • 278. 第一个错误的版本：找到最小的版本 i，使得 isBadVersion(i) = True

2. 查询区间是有序区间，或者通过判断函数每次可减少一半查询区间

上述几个题目中，查询区间都是有序区间，这往往是可以应用二分查找的提示。但是并不是只有有序区间才能使用二分查找，例如 153. 寻找旋转排序数组中的最小值 中的输入数组并不是有序区间，但只要找到一个判断函数，将查询区间的值映射成连续的二元数组，就能使用二分查找。连续的二元数组由一个连续的 False 数组和一个连续的 True 数组组成，例如：

[False, False, False, True, True]

• 猜价格节目中：判断函数是 F(价格 >= 准确价格)，当准确价格为 8 的时候，返回的二元数组为 [False, False, False, False, False, False, False, True, True, True]
• 69. x 的平方根 ：判断函数是 F(i^2 >= x)，当 x = 5 的时候，返回的二元数组为 [False, False, True, True, True]
• 278. 第一个错误的版本：判断函数是 isBadVersion()，当 n 为 5，第一个错误的版本为 2 的时候，二元数组为 [False, True, True, True, True]

由于二元数组中 False 与 True 是连续的，所以每次通过判断函数的返回值，我们都可以减少一半查询区间，结合特点 1，题目通常要求返回的是最后一个 False 或者第一个 True 的位置。

3. 如果解法的时间复杂度是 O(f(n) * log(n)) 的形式，可以尝试考虑二分查找。

解题模式

编写正确的二分查找程序并不容易，不过大部分的二分查找题目都是找到最后一个 False 或者第一个 True 的位置，我们可以通过二分查找的 API 解决问题，用 API 解题有两个好处：

1. 减少代码出错的概率，当你把题目分解成 API 能直接解决的子问题之后，代码量更少，同时因为你熟悉 API 的代码编写，所以不容易出现错误。
2. 对于一些复杂的问题，二分查找只能解决子问题，使用 API 可以让我们专注在题目整体的架构中，而不是纠结于子问题的实现细节上。

常见的编程语言都有内置的二分查找库，其中最常用的两个 API 是 lower_bound 以及 upper_bound，lower_bound 以及 upper_bound 在 Java, Python, C++ 中都有完整的实现，Golang 以及 Rust 实现了 lower_bound，它们的定于如下：

• lower_bound(nums, target) ：找到有序数组 nums 中第一个大于等于 target 的索引值。
• upper_bound(nums, target) ：找到有序数组 nums 中第一个严格大于 target 的索引值。

35. 搜索插入位置

这题的返回值与 lower_bound 的定义一致，可以直接使用它解决，伪代码如下：

searchInsert(nums, target)
    return lower_bound(nums, target)

34. 在排序数组中查找元素的第一个和最后一个位置

如果你要自行实现二分查找解决这题的话会比较复杂而且容易出错，幸运的事，我们能够直接使用 API 来解题：

searchRange(nums, target)
    // 忽略了边界条件的判断
    return [lower_bound(nums, target), upper_bound(nums, target)-1]

有趣的是，因为 nums 里面的都是正整数，所以 upper_bound 也可以用 lower_bound 来代替：

searchRange(nums, target)
    // 忽略了边界条件的判断
    return [lower_bound(nums, target), lower_bound(nums, target+1)-1]

这类能够直接使用 API 的题目还有不少，从我们的经验看来，使用 lower_bound 的使用场景更多。为了能将这些 API 应用在数值比较以外的场景，我们将判断函数抽象了出来，以下为 lower_bound 的伪代码：

LOWER_BOUND(nums, target)
    left, right = 0, nums.length
    while left < right
        mid = left + (right - left) // 2
        if VALID(nums[mid], target)
            right = mid
        else
            left = mid + 1
    return left

VALID(num, target)
    // VALID 函数可以根据题目要求来修改
    if num >= target
        return True
    return False

大部分情况下，我们只需要调整 valid 函数就能够解决二分查找的题目：

69. x 的平方根

mySqrt(x)
    left = 1
    right = x + 1
    while left < right
        mid = left + (right - left) / 2
        if valid(mid, x)
            right = mid
        else
            left = mid + 1
    return left - 1

valid(mid, x)
    if mid * mid > x
        return True
    return False

278. 第一个错误的版本

firstBadVersion(n)
    left = 0
    right = n + 1
    while left < right
        mid = left + (right - left ) // 2
        if valid(mid)
            right = mid
        else left = mid + 1
    return left

valid(mid)
    if isBadVersion(mid):
        return True
    return False

检查代码

在学习如何编写正确的二分查找代码之前，可以先学习循环不变式，《算法导论》的第二章有详细清晰的讲解与例子。我们在此简单介绍，循环不变式通常用来验证代码的正确性，分成初始化，保持，终止三个部分，我们尝试用这个来证明我们最开始的猜价格策略的正确性

• 初始化：根据题意，准确价格在 [1, 11) 这个查询区间内
• 保持：每次猜错的话，新的搜索区间会更新为 [left, mid) （猜得太高）或者 [mid+1, right)（猜得太低），准确价格保持在新的搜索区间内
• 终止：在保持阶段，如果猜中价格的话得到答案。同时由于每次更新查询区间都会减半， while 循环在 left = right 时终止，如果没有找到结果的话，程序能够正常退出。

如果你无法找到判断函数或者需要编写二分查找的变形程序，这时候可以自行编写二分查找程序，我们观察 lower_bound 的实现：

lower_bound(nums, target)
    // 1
    left, right = 0, nums.length
    // 2
    while left < right
        mid = left + (right - left) // 2
        // 3
        if valid(nums[mid], target)
            // 4
            right = mid
        else
              // 4
            left = mid + 1
    return left

常见容易犯错的地方有四点：

1. right 的初始选择是 nums.length 还是 nums.length - 1
2. while 循环的退出条件是 < 还是 <=
3. valid 函数的编写
4. left, right 指针的更新方式是 mid 还是 mid +/- 1

二分查找并没有统一的实现标准，但是注意以下几点：

1. 初始查询区间，注意 right 的开闭性，在以上的 API 实现中，right 是开区间
2. 每次循环后搜索结果都在 [left, right) 组成的区间内
3. valid 函数将查询区间映射成二元数组
4. 区间在找到之前会不断缩小

课后练习

我们推荐了一些合适练习的题目在这里：

• 744. 寻找比目标字母大的最小字母
• 852. 山脉数组的峰顶索引
• 875. 爱吃香蕉的珂珂