特别好用的二分查找法模板（第 2 版）

特别好用的二分查找法模板（第 2 版）

特点：

1、讲算法思想，也讲细节；

2、把细节的地方理解清楚，就不难了，二分法可以轻松掌握。

一、点击视频快速理解

• 「力扣」第 1095 题：山脉数组中查找目标值 题解 （特别推荐，这道题我花了很长时间准备，讲解特别细致）；

• 「力扣」第 35 题：搜索插入位置 题解。

二、学习关键点

• 二分查找算法是典型的「减治思想」的应用，我们使用二分查找将待搜索的区间逐渐缩小，以达到「缩减问题规模」的目的；

• 掌握二分查找的两种思路：

  • 思路 1：在循环体内部查找元素：while (left <= right)；
  • 思路 2：在循环体内部排除元素：while (left < right)。

• 全部使用左闭右闭区间，不建议使用左闭右开区间，反而使得问题变得复杂；

• 不建议背模板，每一步都要清楚为什么这样写，不要跳步，更不能想当然。

三、思路 1：在循环体内部查找元素（解决简单问题时有用）

Java 代码：

class Solution {

    public int search(int[] nums, int target) {
        // 特殊用例判断
        int len = nums.length;
        if (len == 0) {
            return -1;
        }
        // 在 [left, right] 区间里查找 target
        int left = 0;
        int right = len - 1;
        while (left <= right) {
            // 为了防止 left + right 整形溢出，写成如下形式
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                // 下一轮搜索区间：[left, mid - 1]
                right = mid - 1;
            } else {
                // 此时：nums[mid] < target，下一轮搜索区间：[mid + 1, right]
                left = mid + 1;
            }
        }
        return -1;
    }
}

说明：

• 最简单的二分查找思路：在一个有序数组里查找目标元素。特别像以前电视「猜价格」上的猜价格游戏：运气好，一下子猜中，如果主持人说猜高了，下一步就应该往低了猜，如果主持人说猜低了，下一步就应该就往高了猜。这个思路把待搜索区间 [left, right] 分为 3 个部分：

  • mid 位置（只有 1 个元素）；
  • [left, mid - 1] 里的所有元素；
  • [mid + 1, right] 里的所有元素；

• 于是，二分查找就是不断地在区间 [left, right] 里根据 left 和 right 的中间位置 mid = (left + right) / 2 的元素大小，也就是看 nums[mid] 与 target 的大小关系：

  • 如果 nums[mid] == target ，返回 mid；
  • 如果 nums[mid] < target ，由于数组有序，mid 以及 mid 左边的所有元素都小于 target，目标元素可能在区间 [mid + 1, right] 里，因此设置 left = mid + 1；
  • 如果 nums[mid] > target ，由于数组有序，mid 以及 mid 右边的所有元素都大于 target，目标元素可能在区间 [left, mid - 1] 里，因此设置 right = mid - 1。

• 循环体内一定有 3 个分支，并且第 1 个分支一定用于退出循环，或者直接返回目标元素；

• 退出循环以后，left 和 right 的位置关系为 [right, left] ，返回 left 或者 right 需考虑清楚。

注意事项：

• 许多刚刚写的朋友，经常在写 left = mid + 1; 还是写 right = mid - 1; 上感到困惑，一个行之有效的思考策略是：永远去想下一轮目标元素应该在哪个区间里；
  • 如果目标元素在区间 [left, mid - 1] 里，就需要设置设置 right = mid - 1；
  • 如果目标元素在区间 [mid + 1, right] 里，就需要设置设置 left = mid + 1；
• 考虑不仔细是初学二分法容易出错的地方，这里切忌跳步，需要仔细想清楚每一行代码的含义；
• 循环可以继续的条件是 while (left <= right)，特别地，当 left == right 即当待搜索区间里只有一个元素的时候，查找也必须进行下去；
• int mid = (left + right) / 2; 在 left + right 整形溢出的时候，mid 会变成负数，回避这个问题的办法是写成 int mid = left + (right - left) / 2;。

四、思路 2：在循环体内部排除元素（在解决复杂问题时非常有用）

这个版本的模板推荐使用的原因是：需要考虑的细节最少，编码时不容易出错。

根据中间数被分到左边还是右边，一共就以下两种写法。不能死记硬背，应该通过多练习，理解当看到 left = mid 的时候，将取中间数的取法改成上取整的原因。

Java 代码：

public int search(int[] nums, int left, int right, int target) {
    // 在区间 [left, right] 里查找目标元素
    while (left < right) {
        // 选择中间数时下取整
        int mid = left + (right - left) / 2;
        if (check(mid)) {
            // 下一轮搜索区间是 [mid + 1, right]
            left = mid + 1
        } else {
            // 下一轮搜索区间是 [left, mid]
            right = mid
        }
    }
    // 退出循环的时候，程序只剩下一个元素没有看到，视情况，是否需要单独判断 left（或者 right）这个下标的元素是否符合题意
}

Java 代码：

public int search(int[] nums, int left, int right, int target) {
    // 在区间 [left, right] 里查找目标元素
    while (left < right) {
        // 选择中间数时上取整
        int mid = left + (right - left + 1) / 2;
        if (check(mid)) {
            // 下一轮搜索区间是 [left, mid - 1]
            right = mid - 1;
        } else {
            // 下一轮搜索区间是 [mid, right]
            left = mid;
        }
    }
    // 退出循环的时候，程序只剩下一个元素没有看到，视情况，是否需要单独判断 left（或者 right）这个下标的元素是否符合题意
}

理解模板代码的要点：

• 核心思想：虽然模板有两个，但是核心思想只有一个，那就是：把待搜索的目标元素放在最后判断，每一次循环排除掉不存在目标元素的区间，目的依然是确定下一轮搜索的区间；
• 特征：while (left < right)，这里使用严格小于 < 表示的临界条件是：当区间里的元素只有 2 个时，依然可以执行循环体。换句话说，退出循环的时候一定有 left == right 成立，这一点在定位元素下标的时候极其有用；
• 在循环体中，先考虑 nums[mid] 在满足什么条件下不是目标元素，进而考虑两个区间 [left, mid - 1] 以及 [mid + 1, right] 里元素的性质，目的依然是确定下一轮搜索的区间；
  • 注意 1：先考虑什么时候不是解，是一个经验，在绝大多数情况下不易出错，重点还是确定下一轮搜索的区间，由于这一步不容易出错，它的反面（也就是 else 语句的部分），就不用去考虑对应的区间是什么，直接从上一个分支的反面区间得到，进而确定边界如何设置；
• 根据边界情况，看取中间数的时候是否需要上取整；
  • 注意 2： 这一步也依然是根据经验，建议先不要记住结论，在使用这个思想解决问题的过程中，去思考可能产生死循环的原因，进而理解什么时候需要在括号里加 1 ，什么时候不需要；
• 在退出循环以后，根据情况看是否需要对下标为 left 或者 right 的元素进行单独判断，这一步叫「后处理」。在有些问题中，排除掉所有不符合要求的元素以后，剩下的那 1 个元素就一定是目标元素。如果根据问题的场景，目标元素一定在搜索区间里，那么退出循环以后，可以直接返回 left（或者 right）。

以上是这两个模板写法的所有要点，并且是高度概括的。请读者一定先抓住这个模板的核心思想，在具体使用的过程中，不断地去体会这个模板使用的细节和好处。只要把中间最难理解的部分吃透，几乎所有的二分问题就都可以使用这个模板来解决，因为「减治思想」是通用的。好处在这一小节的开篇介绍过了，需要考虑的细节最少。

学习建议：

• 一定需要多做练习，体会这（两）个模板的使用；

• 先写分支逻辑，再决定中间数是否上取整；
• 在使用多了以后，就很容易记住，只要看到 left = mid ，它对应的取中位数的取法一定是 int mid = left + (right - left + 1) / 2;。

五、使用建议

• 简单问题使用思路 1：即要找的那个数的性质特别简单：== 的情况好写，< 的情况好写，> 的情况也好写的时候；
• 复杂问题使用思路 2：即要找的那个数的性质有点复杂，可能需要借助单调性。用思路 2 就可以把两个边界逐渐向中间收缩，直至找到目标元素。
• 区别：
  • 思路 1 循环体内部有 3 个分支，一定有一个分支用于退出循环或者直接返回，因此无需「后处理」；
  • 思路 2 循环体内部有 2 个分支，两个分支都在缩小待搜索区间，退出循环以后，可能需要「后处理」。

六、练习

「力扣」上的二分查找问题主要有以下这三类。这些练习题都可以使用两种二分查找法的思路比较轻松地写出来，并且得到一个不错的分数，大家加油！

1、在数组中查找符合条件的元素的下标

一般而言这个数组是有序的，也可能是半有序的，但不大可能是无序的。

题目	提示与题解
704. 二分查找	二分查找的模板问题，使用本题解介绍的方法就要注意，需要「后处理」。
34. 在排序数组中查找元素的第一个和最后一个位置	查找边界问题，题解（有视频讲解）。
35. 搜索插入位置	题解
33. 搜索旋转排序数组	题解
81. 搜索旋转排序数组 II	题解
153. 寻找旋转排序数组中的最小值	题解
154. 寻找旋转排序数组中的最小值 II	题解
300. 最长上升子序列	二分查找的思路需要理解，代码很像第 35 题，题解。
275. H指数 II	题解
1095. 山脉数组中查找目标值	题解，题解（有视频讲解）
4. 寻找两个有序数组的中位数	二分搜索中最难的问题之一，建议先弄清楚解题思路，题解。

2、在一个有上下界的区间里搜索一个整数

题目	提示与题解
69. 平方根	在一个整数范围里查找一个整数，也是二分查找法的应用场景，题解。
287. 寻找重复数	题解，在一个整数范围里查找一个整数。
374. 猜数字大小	题解

3、判别条件是一个函数

题目	提示与题解
278. 第一个错误的版本
410. 分割数组的最大值	二分搜索中最难的问题之一，判别函数的写法很有技巧。
658. 找到 K 个最接近的元素	题解
875. 爱吃香蕉的珂珂	题解
1300. 转变数组后最接近目标值的数组和	题解

（本节完）