V
主页
折半查找 动画演示 完整代码 二分查找 binary search 数据结构与算法
发布人
【视频支持4k 60帧 更流畅哦】 折半查找也叫二分查找,是一个非常重要的算法 介绍折半查找前,我们先看一个问题 这里有一个数组,共9个元素,分别为从4到50的不同数字 如果我问你27在那个位置上,你应该一眼就能找到他 但是如果你每次只能查看数组中的一个数字,你将如何找出27? 最简单的方法就是从头开始检查每个数字,直到找到27或者到末尾都没有查找到27为止 通过这种方法进行查找的算法,叫做顺序查找 如果我们要查找50呢?是不是也要从头开始找,直到找到为止 当要查找的元素在数组的末尾或者不存在数组中,需要完整遍历数组后才知道 这里有9个元素,所以最坏的情况下需要查找9次 才9次,这看起来没啥问题,但是如果数组中有几百万个元素呢? 这样的话顺序查找会变的非常慢 对于这种情况我们来看看折半查找是如何工作的 我们还是希望查找到27的下标,如果它存在的话 但这一次不是从数组的开头进行逐个查找了 我们从中间位置开始检查,一共有9个元素,中间位置的下标为4 对应的元素值为14,并不是27 但是我们知道数组的所有元素都是按大小进行排序好的,27大于14,所以27只会出现在14的右边 那么前部分我们就可以不用看了 通过这样的操作,我们成功将要查找的次数减少了一半 现在我们继续查找,我们把剩下的数组元素当作一个整体 直接查看它中间索引对应的值,但是这个中间索引在两个索引之间,没关系,在这种情况下我们可以选取左边的元素作为中间索引,稍后在我们讲解代码时你会明白为什么要选取左边 这时索引处的值为30,这意味着27只能在它的左边,所以右边值较大的数组元素就没有必要检索了 我们继续使用折半查找,当前只有一个元素,所以中间只能是它自己了,它就是27 之所以称为折半查找是因为它每次操作都会将数组划分成两部分,直到找到元素或者划分到最小为止 它与顺序查找相比,可以节省大量的查找时间 我们使用折半查找只需要查找三次就可以找到27 顺序查找从第一个元素开始查找,找到27则需要查找6次 但是我们评价一个算法的好坏,并不能从个例出发,而需要考虑其在最坏情况下的时间复杂度 例如我们查找47,它在最末尾处 对于顺序查找需要对比9次 在数组大小为9的情况下,折半查找最坏的情况下只需要查找4次即可 这看起来并没有节省太多的时间 但是如果对含有100万个元素的数组使用折半查找,你觉得需要多少步呢? 可能需要10万步或者1万步? 实际答案是仅需20步 对于100万个元素的数组使用折半查找最坏的情况下仅需20步 这是因为每次迭代中不断地将查找空间分为两半 这意味着它的查找次数实际上是一个对数函数 对于任何大小为n的数组,其最坏情况下都只需要查找log n + 1次 而顺序查找中有100万个数组元素,最坏情况下需要查找100万次 所以其需要查找n次 可以看出二分查找是非常重要的,它能够让我们在较短的时间内查找大量的数据 使用折半查找前,需要满足两个条件 第一个条件是 我们给出的数组元素一定是要按大小进行过排序过的 升序或者降序都可以 当数组不是有序的时,我们查找27,27比14大,应该在右边进行查找 但是现在数组不是有序的,会导致查找失败 第二个条件是 需要满足随机访问的特性 这样我们可以在恒定的时间内跳转到想要达到的位置 这也意味着在其他数据结构中,例如链表中使用折半查找是不行的 折半查找实际上还有很多改进的地方 当我们需要插入新元素时,为了保证不破坏原数组的有序性 首先需要先找到待插入的位置,然后将其后续元素向后移动一位给新元素腾出位置 或者删除元素时,需要将后面的所有元素向前移动一位 解决这些问题时也就促成了二叉搜索树算法的诞生,其可以更有效的插入和删除新元素 根据二叉搜索树又衍生了平衡二叉树、B树等等优秀的算法,在后面课程中我们会逐一介绍
打开封面
下载高清视频
观看高清视频
视频下载器
【强烈推荐】深入浅出数据结构 - 顶尖程序员图文讲解 - UP主翻译校对 (已完结)
数据结构合集 - 折半查找(二分查找)
数据结构与算法:查找(顺序查找,折半查找,索引查找(分块查找))
栈的实现,顺序栈,数组栈,链表栈,完整代码,动画解析,数据结构与算法
折半查找法
【合集】数据结构和算法 完整代码 动画版 考研 期末考试 C和C++版本 数据结构与算法
数据结构可视化神器,包含60+完整算法,AI解析,自定义算法可视化
数据标注员的真是感受
队列、数组队列、链表队列、完整代码动画解析,数据结构与算法
【中文讲解版】国外油管上高质量《数据结构》教程,Google顶尖程序员亲授,完全深度详细讲解。
什么是数组? 完整代码动画版,数据结构与算法 考研 期末考试 C和C++版本
使用动画讲解 二叉树递归遍历的代码,数据结构与算法
哈夫曼编码是如何影响互联网的
二叉树性质、二叉树数组存储、二叉树链表存储 数据结构与算法
[算法竞赛入门] 贪心算法基础 (JSOI24 冬令营)
包含60+算法交互式可视化,完整代码,AI解析,数据结构与算法可视化神器
链表的头插法,数据结构与算法完整代码动画,考研408 期末考试数据结构
什么是树?动画解析,数据结构与算法合集
链表 数据结构与算法,完整代码动画版,附在线数据结构交互式工具
图的数据结构-邻接矩阵法,有向图,无向图的存储方法
《数据结构》算法模拟动画
【点击就送】图码计算机刷题小程序,带AI解析完全免费
【递归】什么是递归?
【算法】贪心算法的理解和思考
数据结构与算法,图的数据结构,动画讲解
【数组-插入】数据结构与算法 完整代码 考研 期末考试 C和C++版本 数据结构与算法
边睡边学算法丨第一期
图的邻接矩阵-代码实现 数据结构与算法
【有挂!!】二叉树遍历秒解,前序遍历、中序遍历、后序遍历
动画讲解 二叉树的存储结构,链表存储 数据结构与算法
全新版本的数据结构和算法可视化
学妹说:“老狗登学长写的代码十字都不能过还是直接弃赛吧。”
长城防火墙识别规则
当你写了一个不太简单的Helloworld
宁愿赔钱也不适配IE的浏览器
数据结构和算法可视化交互式动画版
单链表的带头和不带头结点有啥区别?数据结构与算法
程序员最怕听到一句话:适配IE浏览器???
拉框的手速越来越快了
千万不要做数据标注!!!