二分查找不同模板分析与比较

事件 1：

• 事件 2：前两周我在「力扣」也看到过类似的提问，问的是不知道什么时候写 left = mid，什么时候写 left = mid + 1，帖子找不到了，当时很懒就没有回答；
• 事件 3：在今年九月，就我的题解里面，网友朋友说我写的代码是「左闭右闭」和「左闭右开」还展开了讨论。

看来就「二分查找」我还是没有解释清楚的地方。我在今天的「二分查找不同实现方法细节困惑」这篇帖子里已经做了回复。

在这里就和大家再简单罗列一下我想和大家讲清楚的「二分查找」的各种话题。

1. 二分查找最简单的样子

二分查找最简单的样子是：在一个有序（升序） 整数 数组中查找一个 整数。这道题是「力扣」第 704 题，思路是：找到一个位于搜索区间中间位置的一个元素 nums[mid]：

• 如果 nums[mid] 恰好等于 target，我们就可以说找到了目标元素；
• 如果 nums[mid] < target，由于数组是升序的，target 如果在数组里存在，只能在 mid 的左边，因此下一轮在区间 nums[left..mid - 1] 里继续查找，此时设置 right = mid - 1；
• 如果 nums[mid] > target，由于数组是升序的，target 如果在数组里存在，只能在 mid 的右边，因此下一轮在区间 nums[mid + 1..right] 里继续查找，此时设置 left = mid + 1。

代码如下：

public class Solution {

    public int search(int[] nums, int target) {
        int len = nums.length;
        // 在区间 nums[left..right] 里查找目标元素
        int left = 0;
        int right = len - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                // 下一轮在区间 nums[mid + 1..right] 里搜索
                left = mid + 1;
            } else {
                // 这种情况下，nums[mid] > target
                // 下一轮在区间 nums[left..mid - 1] 里搜索
                right = mid - 1;
            }
        }
        return -1;
    }
}

为什么说这是「二分查找」最简单的样子呢？因为：

• 数组是 整数 数组；
• 数组是 升序 排列；
• 数组里的整数 各不相同；
• 题目要我们找的也是一个 整数。

这种写法就是我们都熟知的《幸运 52》猜价格游戏：

• 要么猜中，我们得到了奖品；
• 如果主持人告诉你猜高了，聪明的你就猜一个更低的价格；
• 如果主持人告诉你猜低了，聪明的你就猜一个更高的价格。

如此往复下去，有限次猜测一定会猜中。

但实际上，我们还遇到过各种各样的问题。题目给出的 条件 变成：数组里有重复元素，要我们找的 答案 变成：

• 第 1 个等于 target 的位置（「力扣」第 34 题）；
• 最后 1 个等于 target 的位置（「力扣」第 34 题）；
• 大于等于 target 的第 1 个位置（「力扣」第 35 题、第 300 题）；等等等等。

2.「力扣」上复杂问题的共同特点

这些问题有一个共同的特点：

如果当前猜的那个数 nums[mid] 符合某个性质，我们还不能确定它一定就是我们要找的元素，必须向左边（或者向右边）继续看下去，才能确定 nums[mid] 是不是我们要找的元素。

例如：找有序整数数组里第 1 个等于 target 的位置（「力扣」第 34 题）。

一种常见的做法是：看到 4 以后，继续向左边「线性查找」，此时时间复杂度变成 O(N) ，这里 N 是数组的长度。实际上正确的做法是：在左边查找的时候 继续使用二分查找。

这里代码大家可以做一下「力扣」第 34 题，我们今天主要解释大家看到的几种写法的差别。

3. 三种常见的模板

我知道二分查找常见有 3 种写法，是在「力扣」的「学习」板块的「LeetBook」里，有一本叫「二分查找」的 LeetBook。

如果你使用英文版的 LeetCode，「学习」版块叫「explore」。

我简单解释一下大家常见的三个模板，它们区分的标志是 while 里面写什么。

• 模板 1：while (left <= right)
• 模板 2：while (left < right)
• 模板 3：while (left + 1 < right)

3.1 模板 1：while (left <= right)

看到 while (left <= right) 这种写法的朋友们，你一定会看到「大佬」们这么用：声明一个 ans 变量，一定会出现在 if 和 else 分支里的其中一个。

以下是「力扣」第 35 题官方题解：

• 题目要我们找的是：第 1 个大于等于 target 的元素的位置，当看到一个元素 nums[mid] 大于等于 target 的时候，nums[mid] 有可能就是我们要找的，所以把 ans 先保存为 mid；
• 数组的长度 n ，也就是数组的最后一个元素的下一个位置也有可能是答案，所以一开始的时候设置 ans = n；
• if 和 else 里面，不管怎么样，left 和 right 的设置都需要 + 1 或者 -1。设置 left = mid + 1，说明下一轮向右边找，设置 right = mid - 1 ，说明下一轮向左边找。这是因为：mid 如果有可能是解的话，因为有了 ans 的设置，一定不会丢失最优解；
• 当 left == right 重合的时候，left 位置的值还没有看到，所以要继续找下去，因此循环可以继续的条件是 while (left <= right)；
• 最后返回的是 ans 哦，不是 left 或者 right 的任何一个。

大家可以在回头看看本文第 2 大点，我复制下来，重要的事情讲 3 遍。

如果当前猜的那个数 nums[mid] 符合某个性质，我们还不能确定它一定就是我们要找的元素，必须向左边（或者向右边）继续看下去，才能确定 nums[mid] 是不是我们要找的元素。

这种写法也叫带 ans 的「二分查找」，「力扣」的巨佬：零神（id：zerotrac）以前就经常用这种写法，现在我不刷题了，所以不知道他是不是还这样写。

3.2 模板 2：while (left < right)

如果你看过我在第 35 题写的题解，就会知道我一直在用这种写法，所以我这里就不展开了。简单说一下：

• while (left < right) 这种写法，我最喜欢的地方是退出循环以后 left 与 right 重合；
• 这种写法我起过很多名字：「两边夹」、「排除法」。它看起来像下面这个样子：

叫「两边夹」是因为这个写法是：两个变量 left 和 right 向中间走，相遇的时候停下。相遇的时候是 left == right，所以循环可以继续的条件是 while (left < right)。

叫「排除法」是每一轮都把一定不是目标元素的值排除掉，下一轮只在有可能存在目标元素的区间里查找。

• 这种写法最难理解的地方是当看到 left = mid 的时候，取中间数需要加 1 。原因在于：整数除法是下取整，取 mid 的时候不能做到真正取到中间位置，例如 left = 3, right = 4， mid = (left + right) / 2 = 3，此时 mid 的值等于 left，一旦进入 left = mid 这个分支，搜索区间不能缩小，因此会进入死循环。

这是很多朋友和我说最难理解的地方，我有两个办法：

• 办法 1：遇到死循环的时候，把 left、right、mid 的值打印出来看一下，例如「力扣」第 69 题。

public class Solution {

    public int mySqrt(int x) {
        // 特殊值判断
        if (x == 0) {
            return 0;
        }
        if (x == 1) {
            return 1;
        }

        int left = 1;
        int right = x / 2;
        // 在区间 [left..right] 查找目标元素
        while (left < right) {
            // 取中间数 mid 下取整时
            int mid = left + (right - left ) / 2;

            // 调试语句开始
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("left = " + left + ", right = " + right + ", mid = " + mid);
            // 调试语句结束

            // 注意：这里为了避免乘法溢出，改用除法
            if (mid > x / mid) {
                // 下一轮搜索区间是 [left..mid - 1]
                right = mid - 1;
            } else {
                // 下一轮搜索区间是 [mid..right]
                left = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int x = 9;
        int res = solution.mySqrt(x);
        System.out.println(res);
    }
}

这里有个小技巧，一般我会在注释里写上「下一轮搜索区间是什么」。如果下一轮搜索区间是 [mid..right] ，这个时候就设置 left = mid，这种情况的反面区间就是 [left..mid - 1] ，那么 else 就设置 right = mid - 1。区间 [mid..right] 和 [left..mid - 1] 组成了原来的整个区间 [left..right] 不用记忆配对关系了。

• 办法 2：暂时不用管这件事情，题目做多了，就慢慢理解了。

「力扣」上很多大佬用的都是这种写法，例如宫水三叶（id：ac_oier），张晴川（id：qingczha）。

这种写法需要注意的地方：

• 看到 mid 的时候一定要清楚两件事情：

1. mid 是不是解；
2. 下一轮向左边找，还是向右边找。

所以就会有「left = mid 与 right = mid - 1」与「left = mid + 1 与 right = mid」这两种区间设置，其实就是一个包含 mid 一个不包含 mid 的区别而已。

分成两个区间，如果分成三个区间，不一定退出循环以后 left 与 right 会重合。

怎么知道 mid 是不是解，下一轮向左边找，还是向右边找，答案是：看题目，重要的事情说三遍，看题目、看题目、看题目。

所以这里还有一个小技巧：分析清楚题目要找的元素需要符合什么性质。

• if 写不符合这个性质，把 mid 排除掉；
• else 就恰好是这个性质。

原因很简单：不符合性质的时候，把 mid 排除掉的逻辑不容易出错（这是个人感觉，评论区有和我一样有同感的朋友）。但是这一点不绝对，我做过的题目只有「力扣」第 287 题例外。

例如「力扣」第 35 题：题目要我们找：第一个大于等于 target 的元素的位置。

所以如果看到的元素 nums[mid] 的值 严格小于 target，mid 肯定不是我们要找的，下一轮应该在右边继续查找，所以下一轮搜索区间是 [mid + 1..right]，设置 left = mid = 1，下面的代码 if 就是这么写出来的。

public class Solution {

    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                // 下一轮搜索区间是 [mid + 1..right]
                left = mid + 1;
            } else {
                // 下一轮搜索区间是 [left..mid]
                right = mid;
            }
        }
        return left;
    }
}

其它细节，由于篇幅的原因就不解释了。大家题目做多了，都能理解到。

3.3 模板 3：while (left + 1 < right)

下面这段代码是我从 LeetBook 里面截图，把需要注意的地方加上了注释。

这种写法的提出者我也不知道是谁，我看蛮多人爱用这种写法的。设计这种写法的想法（好处）和不好的地方，我为大家罗列一下。

• 为了不想判断 mid 是不是保留，把 left 和 right 的设置都写成：left = mid 和 right = mid。表示的意思是都保留了 mid 位置的值，但是不能省去的判断是「下一轮向左走还是向右走」；
• 为了不想出现死循环，把循环可以继续的条件写成了 while (left + 1 < right)，但是不能省去的判断是「退出循环以后」，一定要再判断一下 left 和 right 哪一个才是题目要找的解，这一步有可能会增加一些本来不必要的逻辑（例如「力扣」第 34 题）。

3.4. 我用什么模板

我不固定用哪一种写法，看问题：

• 如果要找的元素性质简单，可以在循环体内决定，我写成 while (lefy <= right)，并且不设置 ans，因为循环体内就可以返回，没有必要设置 ans；
• 如果要找的元素性质稍微复杂，就必须要在退出循环体以后决定，我写成 while (lefy < right)，因为只要仔细的判断，完全可以清楚 mid 是否排除和下一轮向左边走还是向右边走。出现死循环的原因和解决办法我已经完全理解。我写的题解绝大多数都是这种写法，因为「力扣」上的问题绝大多数都是下面这类问题：

（重要的事情说三遍，这是本文第三次出现了）

如果当前猜的那个数 nums[mid] 符合某个性质，我们还不能确定它一定就是我们要找的元素，必须向左边（或者向右边）继续看下去，才能确定 nums[mid] 是不是我们要找的元素。

因此其实重点在 if 和 else 怎么写，再强调一下这个小技巧：分析清楚题目要找的元素需要符合什么性质。

• if 写不符合这个性质，把 mid 排除掉；
• else 就恰好是这个性质。

4. 总结

「二分查找」的确是有很多需要细心的地方，但它不是完全不能掌握的，大家需要有一些耐心，题目做得多了，慢慢就理解了。