• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

❤️【数据结构和算法】动图演示,超详细,就怕你不会!二分查找详解【建议收藏】❤️

互联网 diligentman 1小时前 2次浏览

🎈 作者:Linux猿

🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

🎈 关注专栏:图解数据结构和算法(优质好文持续更新中……)🚀 

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬


目录

🍓一、什么是二分查找算法

🍓二、二分查找算法

🚩2.1 普通二分查找 

⭐2.1.1 算法步骤

⭐2.1.2 动图演示

⭐2.1.3 代码实现

🚩2.2 二分查找下界

⭐2.2.1 算法步骤

⭐2.2.2 动图演示

⭐2.2.3 代码实现

🚩2.3 二分查找上界

⭐2.2.1 算法步骤

⭐2.2.2 动图演示

⭐2.2.3 代码实现

🍓三、STL 中的二分查找函数

🚩3.0 头文件

🚩3.1 普通二分查找

⭐3.1.1 函数介绍

⭐3.1.2 代码示例

🚩3.2 二分查找下界

⭐3.2.1 函数介绍

⭐3.2.2 代码示例

🚩3.3 二分查找上界

⭐3.3.1 函数介绍

⭐3.3.2 代码示例

🍓四、复杂度分析

🚩4.1 时间复杂度

🚩4.2 空间复杂度

🍓五、总结


在数据结构和算法的学习中,需要查找数据时,经常使用到二分查找算法,下面就来详细讲解下二分查找的各种用法。

🍓一、什么是二分查找算法 ?

二分查找算法是在有序序列中查找某一特定元素的查找算法,所谓 “二分”,即:每次查找可以排除一半的元素,所以时间复杂度为 O(log2^n),因此也被称为折半查找(指的是对半排除元素),对数查找(对数指的时间复杂度中的对数)。

________🐌 我是分割线 🐢________

🍓二、二分查找算法

🚩2.1 普通二分查找 

⭐2.1.1 算法步骤

假设存在长度为 n升序 数组 A[],查找元素 target 是否存在

注意:数组降序也是可以的,二分查找一般情况下是升序或降序,符合特定规则的升序和降序也是可以的,比如:两段升序的拼接,这里以升序为例进行讲解。

(0)首先,初始化 left = 0, right = n,表示查找的区间为 [ left,right),最开始时,查找的区间为 [0, n);

(1)计算 left 和 right 的中间节点,中间节点的下标为 mid = (left + right) /2 。

(2)然后,判断 target 与 中间节点值 A[ mid ] 的大小;

(3)如果 target = A[ mid ] ,说明在数组 A 中找到了元素 target,结束查询;

(4)如果 target < A [ mid ] ,说明,target 并不在数组 A 的区间 [mid, right) 中,因为数组 A 是升序数组,所以 target 应该在区间 [left,mid) 中,所以 left 值不变,让 right = mid;

(5)否则,target > A[ mid ],说明,target 在区间 [ mid + 1,right) 中,同样,是因为数组 A 是升序数组,所以 right 的值不变,让 left = mid + 1;

(6)重复步骤 (1)~(5),直到查找到 target 或 left >= right 为止,如果出现 left >= right(这时区间为空,没有元素了),则表示数组 A 中没有找到 target 。

⭐2.1.2 动图演示

来看一下动图演示,假设升序数组 A[] = {1, 3, 5, 7, 9, 11, 13},查找 target = 1,如下所示:

❤️【数据结构和算法】动图演示,超详细,就怕你不会!二分查找详解【建议收藏】❤️
图1 普通二分查找

 在上述动图中,一共查找了三次,第三次 mid = 0,便查找到了 target = 1,具体查找步骤如下所示:

(1)、最开始查找范围为 [0, 7),left = 0, right = 7, 计算 mid = 3;

(2)、缩小查找范围为 left = 0, right = 3,查找范围为 [ 0, 3),重新计算 mid = 1;

(3)、再次缩小查找范围 left = 0, right = 1,查找范围为 [0, 1),重新计算 mid = 0;

(4)、A[ mid = 0 ] = 1 ,查找到 target。

上述就是二分查找数组 A 中 1 的过程。

⭐2.1.3 代码实现

/*
      A[]  : 升序数组,假设要排序的元素为n个
     left  : 排序数组的左边的值,初始为 0
     right : 排序数组的右边的值,初始为 n,切记不是n-1
    target : 要查找的值
*/
int binarySearch(int A[], int n, int target){
    int left = 0, right = n;
    while(left < right){ // 查找的区间为 [left, right)
        int mid = (left + right) / 2; // 更好的方法是:mid = left + (right - left) / 2 能防止溢出
        if(A[mid] == target) return mid;
        else if(A[mid] > target) right = mid;
        else left = mid + 1;
    }
    return -1; // 查找不到
}

在计算 mid 的时候,可以使用如下方式:

mid = left + (right - left) / 2

能够方式 left + right 的溢出。 

🚩2.2 二分查找下界

⭐2.2.1 算法步骤

假设存在长度为 n升序 数组 A[],数组中存在重复的元素,要查找元素 target 的最小下标如下所示:

❤️【数据结构和算法】动图演示,超详细,就怕你不会!二分查找详解【建议收藏】❤️
图2 二分查找下界图

(0)首先,初始化 left = 0, right = n,表示查找的区间为 [ left,right),最开始时,查找的区间为 [0, n);

(1)计算 left 和 right 的中间节点,中间节点的下标为 mid = (left + right) /2 。

(2)然后,判断 target 与 中间节点值 A[ mid ] 的大小;

(3)如果 A[ mid ] >= target,因为查找的是下界,所以 target 在区间 [ left, mid) 区间还可能存在,所以进一步缩小空间,将查找区间缩小为 [left, mid),所以 left 值不变,让 right = mid;

(4)否则,A[ mid ] < target,说明 target 在区间 [ mid + 1,right) 中,因为数组 A 是升序数组,所以 right 的值不变,让 left = mid + 1;

(5)重复步骤 (1)~(4),直到跳出 while 循环;

(6)如果 right 等于 n 或 A [ right ] != target ,则表示未查找到 target,否则 A[ right ]  = target,right 为数组 A 中值为 target 的最小下标;

⭐2.2.2 动图演示

来看一下动图演示,假设升序数组 A[] = {1, 3, 3, 3, 9, 11, 13},查找 target = 3,如下所示:

❤️【数据结构和算法】动图演示,超详细,就怕你不会!二分查找详解【建议收藏】❤️
图3 二分查找下界

 在上述动图中,一共查找了三次,第三次 mid = 0 结束查找(代码中是 left == right 跳出 while 循环)right 指向的值等于 target,具体查找步骤如下所示:

(1)、最开始查找范围为 [0, 7),left = 0, right = 7, 计算 mid = 3;

(2)、因为[0, 3) 中可能还存在 target,缩小查找范围为 left = 0, right = 3,新查找范围为 [ 0, 3),重新计算 mid = 1;

(3)、因为[0, 1) 中可能还存在 target,再次缩小查找范围 left = 0, right = 1,新查找范围为 [0, 1),重新计算 mid = 0;

(4)、left 重新计算后,left == right,结束查找,right 指向的值等于 target。

上述就是二分查找数组 A 中 3 的最小下标的过程。

⭐2.2.3 代码实现

/*
      A[] : 升序数组,假设要排序的元素为 n 个
     left : 查找区间的最左边的下标,初始为 0
    right : 查找区间的最右边的下标,初始为 n
    target: 要查找的值
*/
int lowerSearch(int A[], int n, int target){
    int left = 0, right = n;
    while(left < right){
        int mid = left + (right - left)/2;
        if(A[mid] >= target) right = mid;
        else left = mid + 1;
    }
    if(right == n || A[right] != target)
        return -1;
    return right;
}

注意:需要判断 right 是否是指向 target,因为查找数组中可能就不存在 target。 

🚩2.3 二分查找上界

⭐2.2.1 算法步骤

假设存在长度为 n升序 数组 A[],数组中存在重复的元素,要查找元素 target 的最大下标如下所示:

❤️【数据结构和算法】动图演示,超详细,就怕你不会!二分查找详解【建议收藏】❤️
图4 二分查找上界

(0)首先,初始化 left = 0, right = n,表示查找的区间为 [ left,right),最开始时,查找的区间为 [0, n);

(1)计算 left 和 right 的中间节点,中间节点的下标为 mid = (left + right) /2 。

(2)然后,判断 target 与 中间节点值 A[ mid ] 的大小;

(3)如果 A[mid] > target,所以 target 在区间 [ left,mid) 中,所以缩小空间,将查找区间缩小为 [left, mid),所以 left 值不变,让 right = mid;

(4)否则,A[ mid ] <= target,说明 target 在区间 [ mid + 1,right) 中还可能存在,因为数组 A 是升序数组,所以 right 的值不变,让 left = mid + 1;

(5)重复步骤 (1)~(4),直到跳出 while 循环,left –,因为 left 指向的永远是比 target 大的值的下标;

(6)如果新的 left  等于 n 或 A [ left ] != target ,则表示未查找到 target,否则 A[ left ]  = target,right 为数组 A 中值为 target 的最小下标;

⭐2.2.2 动图演示

来看一下动图演示,假设升序数组 A[] = {1, 3, 3, 3, 9, 11, 13},查找 target = 3,如下所示:

❤️【数据结构和算法】动图演示,超详细,就怕你不会!二分查找详解【建议收藏】❤️
图5 二分查找上界

在上述动图中,一共查找了三次,第三次 mid = 4 结束查找(代码中是 left == right 跳出 while 循环)left – 1 指向的值等于 target,具体查找步骤如下所示:

(1)、最开始查找范围为 [0, 7),left = 0, right = 7, 计算 mid = 3;

(2)、因为[4, 7) 中可能还存在 target,缩小查找范围为 left = 4, right = 7,新查找范围为 [ 4, 7),重新计算 mid = 5;

(3)、因为[4, 5) 中可能还存在 target,再次缩小查找范围 left = 4, right = 5,新查找范围为 [4, 5),重新计算 mid = 4;

(4)、left 重新计算后,left == right,结束查找,left – 1 指向的值等于 target。

上述就是二分查找数组 A 中 3 的最大下标的过程。

⭐2.2.3 代码实现

/*
      A[] : 升序数组,假设要排序的元素为 n 个
     left : 查找区间的最左边的下标,初始为 0
    right : 查找区间的最右边的下标,初始为 n
    target: 要查找的值
*/
int upperSearch(int A[], int n, int target){
    int left = 0, right = n;
    while(left < right){
        int mid = left + (right - left)/2;
        if(A[mid] > target) right = mid;
        else left = mid + 1;
    }
    left--;
    if(left == n || A[left] != target)
        return -1;
    return left;
}

这里需要注意,left 是查找值更大值的下标,所以让 left –,还需要判断一下 left 所指向的值是否是 target,因为可能在查找数组中就不存在 target。 

________🐌 我是分割线 🐢________

🍓三、STL 中的二分查找函数

🚩3.0 头文件

使用 STL 中的二分查找函数,需要引入如下头文件:

#include <algorithm>

🚩3.1 普通二分查找

⭐3.1.1 函数介绍

函数如下所示:

binary_search(A, A + n, target)

其中:

binary_search : 函数名;

A : 查找的数组;

n : 数组 A 的长度; 

target : 查找的目标值

⭐3.1.2 代码示例

#include <iostream>
#include <algorithm> // 头文件
using namespace std;

int main()
{
    int n = 8;
    int A[] = {1, 3, 5, 7, 9, 11, 13, 15};

    cout<<binary_search(A, A + n, 9)<<endl;
    return 0;
}

上述代码中,查找数组 A 中是否存在 9,输出结果为 1。 

🚩3.2 二分查找下界

⭐3.2.1 函数介绍

函数如下所示:

lower_bound(A, A + n, 3) 

其中:

lower_bound : 函数名;

A : 查找的数组;

n : 数组 A 的长度; 

target : 查找的目标值;

注意:函数 lower_bound 返回的是数组目标值最小下标的地址,想要计算下标,需要减去数组 A 的首地址。

⭐3.2.2 代码示例

#include <iostream>
#include <algorithm> // 头文件
using namespace std;

int main()
{
    int n = 8;
    int A[] = {1, 3, 3, 3, 9, 11, 13, 15};

    cout<<lower_bound(A, A + n, 3) - A<<endl;
    return 0;
}

 如上所示,计算下标值需要减去数组 A 的首地址,输出为 1。

🚩3.3 二分查找上界

⭐3.3.1 函数介绍

函数如下所示:

upper_bound(A, A + n, 3) 

其中:

lower_bound : 函数名;

A : 查找的数组;

n : 数组 A 的长度; 

target : 查找的目标值;

注意:函数 upper_bound 返回的是数组目标值第一个大于目标值的地址,想要计算下标,需要减去数组 A 的首地址。

⭐3.3.2 代码示例

#include <iostream>
#include <algorithm> // 头文件
using namespace std;

int main()
{
    int n = 8;
    int A[] = {1, 3, 3, 3, 9, 11, 13, 15};

    cout<<upper_bound(A, A + n, 3) - A<<endl;
    return 0;
}

注意:上述返回的是大于目标值的第一个元素的下标,输出为 4。 

________🐌 我是分割线 🐢________

🍓四、复杂度分析

🚩4.1 时间复杂度

每次查找都是排除一半的情况(缩减一半),相当于每次都除以 2,假设长度为 n,查找次数为 x,则 2^x <= n ,x 约等于 log2^n,所以时间复杂度为 O(log2^n)。

🚩4.2 空间复杂度

通常二分查找并不需要额外的辅助空间,所以空间复杂度为 O(1)。

________🐌 我是分割线 🐢________

🍓五、总结

最长使用的还是普通的二分查找算法,特殊情况会查找上界或下界,当然,可以使用 STL 中的库函数。

欢迎关注下方👇👇👇公众号👇👇👇,获取更多优质内容🤞(比心)!


喜欢 (0)