二分查找学习笔记

二分查找学习笔记

前言

二分查找也称折半查找，它是一种效率较高的查找方法。二分查找，思路很简单，细节是魔鬼。

本文主要探究几个最常用的二分查找场景：寻找一个数、寻找左侧、右侧边界。到底要给 mid 加一还是减一，while 里到底用 <= 还是 <，并给出二分模板。

寻找一个数

寻找一个数的问题是最简单最熟悉的，下面的代码相信你也很熟悉：

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

计算 mid 时需要防止溢出，代码中 left + (right - left) / 2 和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出。

1. while 中为什么是 <=，而不是 < ?

因为二分的区间为左闭右闭的 [left, right]，初始化 right 的赋值是 nums.length - 1

当我们找到了 target 时，即停止搜索

if(nums[mid] == target)
    return mid;

但是如果没找到，搜索区间为空的时候应该终止。

while(left <= right) 的终止条件是 left > right，这个时候搜索区间为空，搜索应终止，举例来说，left = 3，right = 2，这个时候搜索区间为 [3, 2]，应退出循环返回 -1。

while(left < right) 的终止条件是 left >= right，同样举例来说，left = 2，right = 2，按照前面的条件这时候应该终止，但是搜索区间为 [2, 2]，仍然还有元素未被搜索，说明这是错误的。

如果一定要用 while(left < right) 需要额外添加条件：

//...
while(left < right) {
    // ...
}
return nums[left] == target ? left : -1;

2. 为什么更新 left 和 right 时，有些有写 ± 1，有些没有？

不同问题的处理方法不同，这也是容易混淆的点。

对于寻找一个数的问题来说，如果 nums[mid] != target，那么我们就需要去寻找 [left, mid - 1] 或者 [mid + 1, right]，因为 mid 已经查找过了，不需要再次查找。

寻找左（右）侧边界

接下来进一步探讨，寻找左（右）侧边界。

由于左右侧边界的二分查找写法非常多，有的 right = nums.length，有的right = nums.length - 1；有的 left < right，有的 left <= right；有的 return 减 1，有的不减。

下面直接介绍我自己认为比较好用的，好理解的二分模板，仅供参考。

二分模板一共有两个，分别适用于不同情况。

1. 找大于等于给定数的第一个位置 （满足某个条件的第一个数）
2. 找小于等于给定数的最后一个数 （满足某个条件的最后一个数）

• 如果要找左侧边界，即红色端点，用模板 1
• 如果要找右侧边界，即绿色端点，用模板 2

二分查找模板的几个要点

1. 循环条件是 l < r
2. if 的判断条件是让 mid 落在满足你想要结果的区间内
3. 如果更新操作是 r = mid - 1 或者 l = mid，此时为了防止死循环，计算 mid 时需要加 1。
4. 出循环一定是 l == r

模板 1

当我们将区间 [l, r] 划分成 [l, mid] 和 [mid + 1, r] 时，其更新操作是 r = mid 或者 l = mid + 1，计算 mid 时不需要加 1。

• nums[mid] >= target
• nums[mid] < target

int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

对 check 的说明：

判断条件很复杂时用 check 函数，否则 if 后直接写条件即可

例如：nums[mid] >= target

能二分的题一定是满足某种性质，分成左右两部分

模板 2

当我们将区间 [l, r] 划分成 [l, mid - 1] 和 [mid, r] 时，其更新操作是 r = mid - 1 或者 l = mid，此时为了防止死循环，计算 mid 时需要加 1。

• nums[mid] >= target
• nums[mid] < target

int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

关于 mid = l + r + 1 >> 1 为什么要加 1 的问题，

当 l == r - 1 时，mid 会等于 l，那么此时如果执行 l = mid 就死循环了。

浮点数二分

double bsearch_3(double l, double r) {
    const double eps = 1e-6;  // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    return l;
}

例题

• LeetCode 69. x 的平方根
• LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
• LeetCode 35. 搜索插入位置
• LeetCode 74. 搜索二维矩阵
• LeetCode 153. 寻找旋转排序数组中的最小值
• LeetCode 33. 搜索旋转排序数组
• LeetCode 278. 第一个错误的版本
• LeetCode 162. 寻找峰值
• LeetCode 275. H 指数 II

参考

• 二分查找算法模板
• 二分查找细节详解