侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

二分查找

kaixindeken
2021-04-20 / 0 评论 / 0 点赞 / 97 阅读 / 1,866 字

二分查找的引入

在介绍二分查找之前,对于基于数字索引的数组元素的查找,我们可能第一反应都是遍历这个数组,直到给定数组元素值和待查找的值相等时,返回索引值并退出,否则一直遍历到最后一个元素,如果还是没有找到则返回 -1,这样的查找虽然是简单粗暴了点,但是对于规模不大的数据集,也是没什么问题的,不过很明显,对于 n 个元素的数组,这种查找的时间复杂度是 O(n),随着数据规模的增加,性能会越来越差,设想如果数据集的长度是 40 亿(约 2 的 32 次方),那么最差的情况需要遍历数组 40 亿次,简直不敢想象需要花费多长时间!那有没有性能搞好的算法来解决这个问题呢?

在进一步探讨这个问题之前,我们先来看一个生活中的例子。我们日常生活中,很多人应该有这种经历,朋友、同学或者同事淘了个宝贝,神秘兮兮的过来让大家猜多少钱,在约定一个价格范围之后(比如 10-100),大家会七嘴八舌的猜起价格来:

同事A:新淘了个宝贝,猜猜多少钱?

同事B:50块。

同事A:高了。

同事C:30块。

同事A:低了。

同事D:40块。

同事A:高了。

同事E:36块。

同事A:对了。

如果我们用顺序遍历的逻辑,最差需要 91 次,才能猜到价格,现实生活中,没人会这么干,我们采用上面这种逻辑,只需要 4 次就猜到价格了,快了几十倍,而且数据量越大,优势越明显。基于这种思路,我们的算法科学家提炼出了二分查找算法,帮助我们在给定数据集中快速定位要查找的元素。

实现原理

所谓二分查找,针对的是一个有序的数据集合(这点很重要),查找思想有点类似分治思想。每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为 0。注意到二分查找针对的必须是已经排序过的有序数组,否则不能使用该算法。图示如下:

1.png

示例代码

#include <iostream>

int binary_search_internal(int nums[], int num, int low, int high){
    if (low > high){
        return -1;
    }

    int mid = (low + high) / 2;
    if (num > nums[mid]){
        return binary_search_internal(nums, num, mid + 1, high);
    } else if (num < nums[mid] ){
        return binary_search_internal(nums, num, low, mid - 1);
    } else {
        return mid;
    }
}

int binary_search (int nums[], int num){
    return binary_search_internal(nums, num, 0, sizeof(nums) - 1);
}

int main() {
    int nums[] = {1,2,3,4,5,6};
    std::cout << binary_search(nums, 2) << std::endl;
    return 0;
}

性能分析

很显然,二分查找的时间复杂度是 O(logn)。这是一个非常恐怖的数量级,有时候甚至比 O(1) 还要高效,比如我们要在开头提到的 40 亿个数字中查找某一个元素,也只需要32次(2 的 32 次方是 40 亿数量级),这真的是非常高效了,正因如此二分查找在线性表结构中的应用非常广泛。

但是使用二分查找需要注意一个前提,那就是针对有序数组,换言之,二分查找适用于变动不是很频繁的静态序列集,如果序列集变动很频繁,经常进行插入删除操作,那么就要不断维护这个序列集的排序,这个成本也很高,因此,这种情况下就不适用二分查找了,比如我们的数据库查询,增删改查很频繁,显然不是通过二分查找来进行查询的,后面我们会讨论,如何针对动态变化的序列集进行查询操作。

0

评论区