特别好用的二分查找法模板

题目地址	题解
LeetCode 第 35 题：搜索插入位置	特别好用的二分查找法模板（Python 代码、Java 代码）

分析：根据题意，结合题目给出的 4 个示例，不难分析出这个问题的等价表述如下。

1、如果目标值（严格）大于排序数组的最后一个数，返回这个排序数组的长度，否则进入第 2 点。

2、返回排序数组从左到右，大于或者等于目标值的第 1 个数的索引。

事实上，当给出数组中有很多数和目标值相等的时候，我们返回任意一个与之相等的数的索引值都可以，不过为了简单起见，也为了方便后面的说明，我们返回第 1 个符合题意的数的索引。

题目告诉你“排序数组”，其实就是在疯狂暗示你用二分查找法。二分查找法的思想并不难，但写好一个二分法并不简单，就借着这道题为大家总结一下。

一、传统二分查找法模板

刚接触二分查找法的时候，我们可能会像下面这样写代码，我把这种写法容易出错的地方写在了注释里：

Java 代码：

public class Solution {

    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        if (nums[len - 1] < target) {
            return len;
        }

        int l = 0;
        int r = len - 1;

        while (l <= r) {
            int mid = (l + r) / 2;
            // 等于的情况最简单，我们放在第 1 个分支进行判断
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                // 题目要我们返回大于或者等于目标值的第 1 个数的索引
                // 此时 mid 一定不是所求的左边界，
                // 此时左边界更新为 mid + 1
                l = mid + 1;
            } else {
                // 既然不会等于，此时 nums[mid] > target
                // mid 也一定不是所求的右边界
                // 此时右边界更新为 mid - 1
                r = mid - 1;
            }
        }
        // 注意：一定得返回左边界 l，
        // 如果返回右边界 r 提交代码不会通过
        // 下面我尝试说明一下理由，如果你不太理解下面我说的，那是我的表达问题
        // 【注意】建议你不要纠结这个问题，因为我马上介绍的二分法模板，可以避免对返回 l 和 r 的思考

        // 理由是对于 [1,3,5,6]，target = 2，返回大于等于 target 的第 1 个数的索引，此时应该返回 1
        // 在上面的 while (l <= r) 退出循环以后，r < l，r = 0 ，l = 1
        // 根据题意应该返回 l，
        // 如果题目要求你返回小于等于 target 的所有数里最大的那个索引值，应该返回 r

        return l;
    }
}

说明：如果你把二分查找法可以进行的条件写成 while (l <= r) 的话，在写最后一句 return 的时候，如果你不假思索，把左边界 l 返回回去，可能误打误撞，你写对了。但是事实上，返回 l 是有一定道理的，如果题目换一种问法，你可能就要返回右边界 r，这句话不太理解没有关系，我也不打算讲得很清楚，因为太绕了，这不是我要说的重点。

传统二分查找法的问题在于，当退出 while 循环的时候，应该返回左边界还是右边界比较容易出错。

那么是不是可以回避这个问题呢？答案是肯定的，并且只要你掌握了下面我介绍的“神奇的”二分查找法模板，你会屡试不爽的。

二、“神奇的”二分查找法模板

在一些资料中，你可能看过别人写二分查找法，把循环可以进行的条件写成 while (l < r) ，当时你是不是跟我一样有疑问，咦？当左右边界一样的时候，那个数岂不是会被漏掉。但是我要告诉你，这样写是最好的，这是最好二分查找法“模板”的一部分。

理由很简单，写 while (l < r) 的时候，退出循环时，左边界等于右边界，因此你不必纠结要返回 l 还是 r ，此时返回 l 或者 r 都是可以的。

二分查找法之所以高效，是因为它利用了数组有序的特点，在每一次的搜索过程中，都可以排除将近一半的数，使得搜索区间越来越小，直到区间成为一个数。不过这里有个细节要注意：

1、如果你确定你要找的数一定在左边界和右边界所表示的区间里出现，那么可以放心地返回 l 或者 r；

2、如果你不确定你要找的数一定在左边界和右边界所表示的区间里出现，那么也没有关系，只要在退出循环以后，再针对 nums[l] 或者 nums[r] （此时 nums[l] == nums[r]）单独作一次判断，看它是不是你要找的数即可。

写 while (l < r) 可以避免你对返回左边界还是右边界的讨论。下面给出这道问题，使用 while (l < r) 模板写法的参考代码。

Python 代码：

class Solution:

    def searchInsert(self, nums, target):
        # 返回大于等于 target 的索引，有可能是最后一个
        size = len(nums)
        if size == 0:
            return 0
        l = 0
        # 如果 target 比 nums里所有的数都大，则最后一个数的索引 + 1 就是候选值，因此，右边界应该是数组的长度
        r = size

        # 二分的逻辑一定要写对，否则会出现死循环或者数组下标越界
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid
        return l

Java 代码：

public class Solution {

    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        if (target > nums[len - 1]) {
            return len;
        }
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }
}

不过写出这段代码还是有一定“技巧”的。

三、技巧、调试方法和注意事项

1、首先，得弄清楚取中点的方式。

（1）当 l 和 r 是很大的整数的时候，你写 int mid = (l + r) / 2; 这里 l + r 就有可能超过 int 类型能表示的最大值，因此使用 mid = l + (r - l) // 2 可以避免这种情况。

事实上 mid = l + (r - l) // 2 在 r 很大，并 l 是负数且很小的时候， r - l 也有可能超过 int 类型能表示的最大值，只不过一般情况下 l 和 r 表示的是数组索引值，l 是非负数，因此 r - l 溢出的可能性很小。

（2）另外还要注意，当数组的元素个数是偶数的时候，中位数有左中位数和右中位数之分：

• 使用 mid = l + (r - l) // 2 得到左中位数的索引；
• 使用 mid = l + (r - l + 1) // 2 得到右中位数的索引。

当数组的元素个数是奇数的时候，二者都能选到最中间的那个中位数。

我们使用一个具体的例子来验证这件事情，当索引 l = 3，索引 r = 4 的时候，左中位数是索引 l，右中位数是索引 r，这是因为：

mid = l + (r - l) // 2 = 3 + (4 - 3) // 2 = 3 + 0 = 3，

mid = l + (r - l + 1) // 2 = 3 + (4 - 3 + 1) // 2 = 3 + 1 = 4。

记忆方法：(r - l) 不加 1 选左中位数，加 1 选右中位数。

那么，什么时候使用左中位数，什么时候使用右中位数呢？这就要看分支的逻辑了。

2、编写分支的逻辑循序先写“排除逻辑”所在的分支。

这里介绍很重要的一个技巧：先考虑能把“中位数”排除在外的逻辑，而不能排除“中位数”的逻辑放在 else 分支里，这样做的理由有 2 点：

（1）可以排除“中位数”的逻辑，通常比较好想，但并不绝对，这一点视情况而定；

（2）分支条数变成 2 条，比原来 3 个分支要考虑的情况少，即不用单独考虑中位数是否满足题意，因为退出循环的时候，左右区间压缩成一个数（索引）的时候，这个索引表示的数要么满足题意，要么不满足题意，而不必在二分逻辑中单独做判断（这一点很重要，希望读者结合具体例子仔细体会）。

以本题为例，最开始我们就分析了要求我们找到“大于或者等于目标值的第 1 个数的索引”。所以对于这道题而言：

（1）如果中位数小于目标值，就应该被排除，左边界 l 就至少是 mid + 1；

（2）如果中位数大于等于目标值，还不能够肯定它就是我们要找的数，因为要找的是等于目标值的第 1 个数的索引，中位数以及中位数的左边都有可能是符合题意的数，因此右边界就不能把 mid 排除，因此右边界 r 至多是 mid，此时右边界不向左边收缩。

而下一点就更关键了。

3、根据分支编写的情况，选择使用左中位数还是右中位数。

先写分支，根据分支的逻辑选中位数，选左中位数还是右中位数，这要做的理由是为了防止出现死循环。

死循环就容易发生在区间元素只有 2 个时候，此时中位数的选择尤为关键。

为了避免出现死循环，我们需要确保：

1、如果分支的逻辑，在选择左边界的时候，不能排除中位数，那么中位数就选“右中位数”，只有这样区间才会收缩，否则进入死循环；

2、同理，如果分支的逻辑，在选择右边界的时候，不能排除中位数，那么中位数就选“左中位数”，只有这样区间才会收缩，否则进入死循环。

上面的规则说起来很绕，可以暂时跳过，不要去记它，我写的时候都晕。理解上面的这个规则可以通过具体的例子：

针对以上规则的第 1 点：如果分支的逻辑，在选择左边界的时候不能排除中位数，例如：

Python 伪代码：

while l < r:
      # 不妨先写左中位数，看看你的分支会不会让你代码出现死循环，从而调整
    mid = l + (r - l) // 2
    # 业务逻辑代码
    if (check(mid)):
        # 选择右边界的时候，可以排除中位数
        r = mid - 1
    else:
        # 选择左边界的时候，不能排除中位数
        l = mid

• 在区间中的元素只剩下 2 个时候，例如：l = 3，r = 4。此时左中位数就是左边界，如果你的逻辑执行到 l = mid 这个分支，且你选择的中位数是左中位数，此时左边界就不会得到更新，区间就不会再收缩（理解这句话是关键），从而进入死循环；
• 为了避免出现死循环，你需要选择中位数是右中位数，当逻辑执行到 l = mid 这个分支的时候，因为你选择了右中位数，让逻辑可以转而执行到 r = mid - 1 让区间收缩，最终成为 1 个数，退出 while 循环。

上面的这种情况如果你理解了，就可以类似地理解提出的规则的第 2 点。

按照我的经验，一开始编码的时候，稍不注意就很容易出现死循环，不过没有关系，你可以你的代码中写上一些输出语句，就容易理解“在区间元素只有 2 个的时候容易出现死循环”。具体编码调试的细节，可以参考我在 「力扣」第 69 题：x 的平方根的题解《二分查找 + 牛顿法（Python 代码、Java 代码）》 。

四、使用总结

总结一下，我爱用这个模板的原因、技巧、优点和注意事项：

1、原因：无脑地写 while l < r: ，这样你就不用判断，在退出循环的时候你应该返回 l 还是 r；

2、技巧：先写分支逻辑，并且先写排除中位数的逻辑分支（因为容易想到），再根据分支的情况选择使用左中位数还是右中位数；

3、优点：分支条数只有 2 条，代码执行效率更高，不用单独判断中位数是否符合题目要求，写分支的逻辑的目的是尽量排除更多的候选元素，而判断中位数是否符合题目要求我们放在最后进行，这就是第 5 点；

4、注意事项 1：左中位数还是右中位数选择的标准根据分支的逻辑而来，标准是每一次循环都应该让区间收缩，在区间只剩下 2 个元素的时候，为了避免死循环发生，选择正确的中位数类型。如果你实在很晕，不防就使用有 2 个元素的测试用例，就能明白其中的原因，另外在代码出现死循环的时候，建议你可以将左边界、右边界、你选择的中位数的值，还有分支逻辑都打印输出一下，出现死循环的原因就一目了然了；

5、注意事项 2：如果能确定要找的数就在候选区间里，那么退出循环的时候，区间最后收缩成为 1 个数后，直接把这个数返回即可；如果你要找的数有可能不在候选区间里，区间最后收缩成为 1 个数后，还要单独判断一下这个数是否符合题意；

最后给出两个模板，大家看的时候看注释，而不必也无需记忆它们，最好的理解这个模板的方法还是应用它。

Python 伪代码1： 分支是右区间不收缩的时候，选中位数选左中位数，因为如果你选右中位数，会出现死循环。

def binary_search_1(l, r):
    # 当分支逻辑不能排除右边界的时候选择左中位数
    # 如果选择右中位数，当区间只剩下 2 个元素的时候，
    # 一旦进入 r = mid 这个分支，右边界不会收缩，代码进入死循环
    while l < r:
        mid = l + (r - l) // 2
        if check(mid):
            # 先写可以排除中位数的逻辑
            l = mid + 1
        else:
            # 右边界不能排除
            r = mid
    # 退出循环的时候，视情况，是否需要单独判断 l （或者 r）这个索引表示的元素是否符合题意

Python 伪代码2：分支是左区间不收缩的时候，选中位数选右中位数，因为如果你选左中位数，会出现死循环。

def binary_search_2(l, r):
    # 当分支逻辑不能排除左边界的时候选择右中位数
    # 如果选择做中位数，当区间只剩下 2 个元素的时候，
    # 一旦进入 l = mid 这个分支，左边界不会收缩，代码进入死循环
    while l < r:
        mid = l + (r - l + 1) // 2
        if check(mid):
            # 先写可以排除中位数的逻辑
            r = mid - 1
        else:
              # 左边界不能排除
            l = mid
    # 退出循环的时候，视情况，是否需要单独判断 l （或者 r）这个索引表示的元素是否符合题意

说明：我写的时候，一般是先默认将中位数写成左中位数，再根据分支的情况，看看是否有必要调整成右中位数，即是不是要在 (r - l) 这个括号里面加 1 。

我想我应该是成功地把你绕晕了，在此建议您不妨多做几道使用“二分查找法”解决的问题，用一下我说的这个模板，在发现问题的过程中，体会这个模板好用的地方，相信你一定会和我一样爱上这个模板的。

转载:https://liwei.party/2019/06/17/leetcode-solution-new/search-insert-position/