牛易疯先森的开发记录
0%

二分查找

发表于 分类于

二分查找，就是在一个区间内查找某个值(eg: target)的时候，每次把区间一分为二，然后选择满足性质的区间(即包含 target)继续一分为二，直到区间长度为一。

最开始刷二分题的时候，比较慢，可能自己没整理好的一个通用的思路，自从用了 y总 的模板后，就离不开了，真的很爽。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
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;
}

作者：yxc
链接：https://www.acwing.com/blog/content/277/

其实，上面模板的代码分别对应两种情况

  • bsearch_1: 找左边界，不断的向左逼近，比如：求 >=x 的最小值
  • bsearch_2: 找右边界，不断的向右逼近，比如：求 <=x 的最大值

画个图，来加深下理解；

上图中，红色的区间是满足性质的，反之绿色的则不满足性质，而模板中的 check(mid) 函数就是用来判断是否满足性质，从而将区间一分为二。

  • bsearch_1
    • true: 满足性质，区间变成：[l, mid], 不断的向左逼近，找左边界
    • false: 不足，区间变成：[mid+1, r]
  • bsearch_2
    • true: [mid, r], 不断的向右逼近，找右边界
    • false: [l, mid-1]

注意点

  1. 循环退出条件是 while(l < r), 不是 while(l <= r)；因为当 while(l < r) 时，当条件是 l >= r 就会退出，而这里则是 l == r；
  2. check(mid) 是用来判断 mid 是否满足某种性质的，并且 mid 是在所满足性质区间内的；
  3. bsearch_2 里面的 mid = l + r + 1 >> 1;，对比 bsearch_1 为什么要加 +1 呢？因为 C++ 是下取整的，当 l = r-1 时，mid = l+r>>1 = r+r-1>>1 = r-1=l，当满足性质时，l = mid = l，此时 l 的值没发生变化，这样就发生死循环了

解题思路

解题思路总结：

  1. 先画图，确定二分的边界(找左边界还是右边界)
  2. 根据边界来设计一个check 函数（满足某种性质）
  3. 判断区间怎么更新，决定是 l = mid 还是 r = mid

练习

刷几道 lc 来找下感觉，巩固下模板知识。

704. 二分查找

704. 二分查找.

一道很基础的题目，在升序数组里面找一个数，这里即可以找左边界，也可以找右边界，按上面的解题思路总结来考虑一下这道题。

  1. 左边界(bsearch_1)
    1. check 函数：nums[mid] >= target，则不断的向左逼近
    2. 因为是找左边界，所以是 r = mid；
  2. 右边界(bsearch_2)
    1. check 函数：nums[mid] <= target，则不断的向左逼近（跟左边界的代码是相对的）
    2. 因为是找右边界，所以是 l = mid；

bsearch_1

找左边界，不断的向左逼近，找 >= target 的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[l] != target) return -1;
        return l;
    }
};

bsearch_2

找右边界，不断的向右逼近，找 <= target 的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while (l < r) {
            int mid = (l+r+1) >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid-1;
        }
        if (nums[l] != target) return -1;
        return l;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置

这题跟上题是一样的思路，套用模板直接求第一个位置和最后一个位置的数即可。

  • 第一个位置：见 704. 二分查找 - bsearch_1;
  • 最后一个位置：见 704. 二分查找 - bsearch_2;

33. 搜索旋转排序数组

33. 搜索旋转排序数组

这道题目的数据并不是单调的，但也是可以用二分的，我们需要发现其中的性质。

发现上面的数据是有二段性的，即两个区间是有序的，如果我们能确定 target 在某一个区间，那么就可以在这个区间里面用二分了。
那怎么确定 target 在哪一个区间呢？这个简单，由于数组没有重复元素，第一段的最小值肯定大于第二段的最大值，我们只需要用 target 跟第二段的最大值（即数组最后一个元素）作比较即可。
那我们怎么判断找到这两个区间呢？也就是找到一个位置，把数组分成两个区间，可以遍历一次，如果 nums[i+1] 小于 nums[i]，则说明 [0, i] 属于第一段，而 [i+1, n-1] 属于第二段，是否能用二分找到这个区间呢？也就是找到这个区间的最大值或者最小值，然后根据这里两个极值把数组分成两个区间。
我们先以求最大值为例。

最大值

按上面的解题思路总结来考虑一下这道题。

  1. 边界在哪？求最大值，有因为是递增的，肯定在右边
  2. check 函数？>= nums[0] 就行，不断向右逼近
  3. 区间更新？向右逼近，肯定是 l = mid;

好，开干。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }
        // l 和 r 就是最大值的下标
        if (target <= nums.back()) { // 在第二个区间
            l++, r = nums.size()-1;
        } else {
            l = 0;
        }
        /* 
        防止某种 case: [1], 0 的情况，导致
        l = 1, r = 0 的情况。
        */
        if (l > r) {
            l = 0, r = nums.size() - 1;
        }
        // bsearch_2, 这里用 bsearch_1 也是 OK 的，同 704
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid-1;
        }
        if (nums[r] != target) return -1;
        return r;
    }
};

最小值

解题思路同上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] <= nums.back()) r = mid;
            else l = mid + 1;
        }
        // l 和 r 就是最大值的下标
        if (target <= nums.back()) { // 在第二区间
            r = nums.size()-1;
        } else {
            l = 0, r--;
        }
        // bsearch_1, 这里用 bsearch_2 也是 OK 的，同 704
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid+1;
        }
        if (nums[l] != target) return -1;
        return l;
    }
};

用这里找最小值的思路就能解决 153. 寻找旋转排序数组中的最小值 了。

81. 搜索旋转排序数组 II

81. 搜索旋转排序数组 II

跟 33 的区别在于：这道题有重复数，那这个思路还行的同吗？

通过 33 的图，并结合这里的题意可知，只有第一个区间前面的数和第二个区间后面的数会重复，而这里题意是 编写一个函数来判断给定的目标值是否存在于数组中。，所以我们把重复数给移除掉的话，是不影响结果的，这样就能用 33 的思路来解决了，具体思路见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        int R = r;
        while (R >= 0 && nums[0] == nums[R]) R--;
        // 数组元素全相同
        if (R < 0) return nums[0] == target;
        
        l = 0, r = R;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid-1;
        }

        if (target >= nums[0]) {
            l = 0;
        } else {
            l++, r = R;
        }
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid-1;
        }
        // 前面 l++ 可能会导致 l > r
        return nums[r] == target;
    }
};

用这种去重的思路，同样能解决 154. 寻找旋转排序数组中的最小值 II。

69. x 的平方根

69. x 的平方根

  1. 确定边界？这里需要返回一个数开平方根后的整数，如果一个数开平方根后的值 result 恰好是整数，那就直接返回 result ；如果是小数呢？结合题目的 示例 2 可知，应该返回 <= result 的最大整数，所以这里是找右边界；
  2. check 函数？ mid <= x/mid
  3. 区间更新？向右逼近，肯定是 l = mid;
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x;
        while (l < r) {
            // +1ll, 防止 int 数据溢出
            int mid = (l+r+1ll) >> 1;
            if (mid <= x/mid) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

思考

Q: 找左边界可以吗？
A: 当然是可以的，不过逻辑稍微会复杂点，因为 C++ 里除法是下取整，所以划分的区间是 [0, [mid][下取整]] 和 [[mid][下取整]+1, x]，所以最后得到答案是 [mid][下取整]+1，所以需要做 -1 操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int mySqrt(int x) {
        // 防止 case: 1 时，后面出现 mid 为 0 的情况
        if (x < 2) return x;
        int l = 0, r = x;
        while (l < r) {
            // +1ll, 防止 int 数据溢出
            int mid = (l+(long long)r) >> 1;
            if (mid >= x/mid) r = mid;
            else l = mid+1;
        }
        if (l == x/l) return l;
        return l-1;
    }
};

还是上一个做法比较简单，符合常规思考逻辑。

总结

  1. 按照 解题思路 多做题目，熟能生巧；
  2. 有些题目二分性质不是那么明显，不能套用模板，但是思路还是通用的（后面再讲）