6

二分查找

 4 years ago
source link: http://joakimliu.github.io/2021/01/23/binary-search/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

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

模板 

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 的最大值

画个图，来加深下理解；

MNbEBbM.jpg!mobile

上图中，红色的区间是满足性质的，反之绿色的则不满足性质，而模板中的 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) 
    nums[mid] >= target
r = mid
  2. 右边界(bsearch_2) 
    nums[mid] <= target
l = mid

bsearch_1

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

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 的最大值。 

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. 搜索旋转排序数组

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

vuuE7z6.jpg!mobile

发现上面的数据是有二段性的，即两个区间是有序的，如果我们能确定 target 在某一个区间，那么就可以在这个区间里面用二分了。

那怎么确定 target 在哪一个区间呢？这个简单，由于数组没有重复元素，第一段的最小值肯定大于第二段的最大值，我们只需要用 target 跟第二段的最大值（即数组最后一个元素）作比较即可。

那我们怎么判断找到这两个区间呢？也就是找到一个位置，把数组分成两个区间，可以遍历一次，如果 nums[i+1] 小于 nums[i] ，则说明 [0, i] 属于第一段，而 [i+1, n-1] 属于第二段，是否能用二分找到这个区间呢？也就是找到这个区间的最大值或者最小值，然后根据这里两个极值把数组分成两个区间。

我们先以求最大值为例。

最大值

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

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

好，开干。

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;
    }
};

最小值

解题思路同上。

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 的思路来解决了，具体思路见代码。 

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; 
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 操作。 

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. 有些题目二分性质不是那么明显，不能套用模板，但是思路还是通用的（后面再讲）

report

Recommend

  • 47
    • www.ydstudio.net 6 years ago
    • Cache

    Java实现二分查找算法

    二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。所以在采用二分法查找时，数据需是有序不重复的，如果是无序的也可通过选择排序、冒泡排序等数组排序方法进行排序之后，就可以使用二分法查找。 基本...

  • 52
    • studygolang.com 6 years ago
    • Cache

    数据结构与算法：二分查找

    二分查找是搜索算法中的一种，用来搜索 有序数组 二分查找：...

  • 67
    • 掘金 juejin.im 5 years ago
    • Cache

    面试官，我会写二分查找法了！对，没有 bug 的那种！

    前言科普 第一篇二分搜索论文是 1946 年发表，然而第一个没有 bug 的二分查找法却是在 1962 年才出现，中间用了 16 年的时间。 2019 年的你，在面试的过程中能手写出没有 bug 的二分查找法么？ 定义 在计算机科学中，二分查找（英语：bina

  • 29
    • www.cnblogs.com 5 years ago
    • Cache

    实现 sqrt(x)：二分查找法和牛顿法

    最近忙里偷闲，每天刷一道 LeetCode 的简单题保持手感，发现简单题虽然很容易 AC，但若去了解其所有的解法，也可学习到不少新的知识点，扩展知识的广度。 创作本文的思路来源于：

  • 21
    • 微信 mp.weixin.qq.com 4 years ago
    • Cache

    二分查找及对应的几道经典题目

    ↑ 点击上方蓝字" 奶糖猫 ",加个关注如何 本文约2500字，阅读大概需要10分钟 二分查找(Binary Search)属于七大查找算法之一，又称折半查找，它的...

  • 29
    • www.cnblogs.com 4 years ago
    • Cache

    二分查找及其变种算法

    目录 前言 概念：二分查找（Binary Search）算法，一种针对有序数据集合的查找算法，也叫折半查找算法。 思想：二分查找针对的是一个 有序的数据集合 ( 升序或降序 )，查找思想有点类似...

  • 10
    • labuladong.github.io 4 years ago
    • Cache

    如何运用二分查找算法

    如何运用二分查找算法 👆让天下没有难刷的算法！若 GitBook 访问太慢，可尝试

  • 17
    • itimetraveler.github.io 4 years ago
    • Cache

    ”二分查找“算法的时间复杂度

    ”二分查找“算法的时间复杂度 算法的时间复杂度无非就是for、while等包含起来的基本运算单元的循环次数 1、二分查找二分查找（binary search...

  • 7
    • blogread.cn 4 years ago
    • Cache

    你是那10%可以实现二分查找算法的程序员吗？

    你是那10%可以实现二分查找算法的程序员吗？ 浏览:5918次  出处信息 原文链接：

  • 10
    • blog.csdn.net 4 years ago
    • Cache

    数据结构之二分查找

    数据结构之二分查找

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK