二分查找

• 二分查找
  • 1. 介绍
    • 1.1. 概述
    • 1.2. 思维导图
  • 2. 详细介绍
    • 2.1. 简单模板
    • 2.2. while循环的条件
      • 2.2.1. 为什么 while 循环的条件中是 <= 而不是 <
      • 2.2.2. <= 和 < 结束的临界值是什么
    • 2.3. 停止搜索的临界条件
    • 2.4. 中间值mid
    • 2.5. 二分的区间划分
  • 3. 示例
    • 3.1. 基础二分查找
    • 3.2. 向下取整
    • 3.3. 向上取整
  • 4. 总结
• 参考

该文记录二分查找的主要思想。

二分查找

1. 介绍

1.1. 概述

• 待查找的数是有序的
• 每次折半来缩小区间查找

比如我们在已知的有序序列中查找数字7，那么经过以下折半，则三次即可查找完成。

二分查找并不简单，Knuth 大佬（发明 KMP 算法的那位）都说二分查找：思路很简单，细节是魔鬼。很多人喜欢拿整型溢出的 bug 说事儿，但是二分查找真正的坑根本不是那个细节问题，而是在于到底要给 mid 加一还是减一，while 里到底用 <= 还是 <。

1.2. 思维导图

图片内容来自liweiwei1419

2. 详细介绍

2.1. 简单模板

class Solution {
public:
    int search(vector<int> &nums, int target) {
        // 在 [left, right] 区间里查找 target
        int left = 0;
        int right = nums.size() - 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;
    }
};

2.2. while循环的条件

2.2.1. 为什么 while 循环的条件中是 <= 而不是 <

因为初始化 right 的赋值是 nums.size() - 1，即最后一个元素的索引，而不是 nums.size()。这二者可能出现在不同功能的二分查找中，区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引大小为 nums.size() 是越界的。文中所有的算法都是基于前者 [left, right] 两端都闭的区间。这个区间其实就是每次进行搜索的区间。

2.2.2. <= 和 < 结束的临界值是什么

• <=：right == left - 1

• <：right == left

---

2.3. 停止搜索的临界条件

什么时候应该停止搜索呢？当然，找到了目标值的时候可以终止：

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

但如果没找到，就需要 while 循环终止，然后返回 -1。那 while 循环什么时候应该终止？搜索区间为空的时候应该终止，意味着你没得找了，就等于没找到嘛。

while(left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧，这个集合为空集。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

while(left < right) 的终止条件是 left == right，写成区间的形式就是 [left, right]，或者带个具体的数字进去 [2, 2]，这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。

当然，如果你非要用 while(left < right) 也可以，我们已经知道了出错的原因，就打个补丁好了：

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

---

2.4. 中间值mid

• int mid = (left + right) / 2; 在 left + right 整形溢出的时候，mid 会变成负数，回避这个问题的办法是写成 int mid = left + (right - left) / 2;。

int mid = (left + right) / 2;			// 整型溢出
int mid = left + (right - left) / 2;	// 推荐

• / 2 表示的是下取整，当数组中的元素个数为偶数的时候，int mid = left + (right - left) / 2; 只能取到位于左边的那个元素。

取右边中间数的表达式是（其实就是在括号里 + 1，表示上取整）：

int mid = left + (right - left + 1) / 2;

---

2.5. 二分的区间划分

为什么 left = mid + 1，right = mid - 1？有的代码是 right = mid 或者 left = mid，没有这些加1减1，到底怎么回事，怎么判断？

答：刚才明确了【搜索区间】这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，下一步应该去搜索哪里呢？当然是去搜索 [left, mid-1] 或者 [mid+1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。

• left = mid + 1，right = mid - 1我们是将区间划分成了三个部分

• left = mid或者right = mid我们划分了两个区间

3. 示例

3.1. 基础二分查找

• 范围在[left, right]闭区间中，left = 0、right = arr.length - 1；
• 注意循环条件为 left <= right

class Solution {
public:
    int search(vector<int> &nums, int target) {
        // 在 [left, right] 区间里查找 target
        int left = 0;
        int right = nums.size() - 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] 里的所有元素；

循环可以继续的条件是 while (left <= right)，特别地，当 left == right 即当待搜索区间里只有一个元素的时候，查找也必须进行下去；

704. 二分查找

3.2. 向下取整

int search(vector<int> &nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    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）这个下标的元素是否符合题意
    // return nums[left] == target ? left : -1;
}

278. 第一个错误的版本

3.3. 向上取整

int search(vector<int> &nums, int target) {
        int left = 0;
    int right = nums.size() - 1;
    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）这个下标的元素是否符合题意
    // return nums[left] == target ? left : -1;
}

69. x 的平方根

4. 总结

除了本文所介绍的二分查找的应用方式，二分查找其实还有很多其他的变体和应用，但它们基本上是循环条件，判断条件，边界更新方法的不同组合，例如，有的二分查找的循环条件可以是 while(left + 1 < right)，有的边界的更新的条件需要依赖 nums[left], nums[mid], nums[mid+1], nums[right]四个值的相互关系。

查找方式	循环条件	左侧更新	右侧更新	中间点位置	返回值
标准二分查找	left <= right	left = mid + 1	right = mid -1	left + (right - left) / 2	-1/mid
二分找左边界	left < right	left = mid - 1	right = mid	left + (right - left) / 2	-1/left
二分找右边界	left < right	left = mid	right = mid - 1	left + (right - left + 1) / 2	-1/left

参考

[1] https://github.com/ojeveryday/AlgoWiki/blob/master/BinarySearch/README.md