算法系列15天速成——第四天 五大经典查找【上】

系统 1803 0

在我们的生活中,无处不存在着查找,比如找一下班里哪个mm最pl,猜一猜mm的芳龄.......对的这些都是查找。

在我们的算法中,有一种叫做线性查找。

分为:顺序查找。

折半查找。

查找有两种形态:

分为:破坏性查找, 比如有一群mm,我猜她们的年龄,第一位猜到了是23+,此时这位mm已经从我脑海里面的mmlist中remove掉了。

哥不找23+的,所以此种查找破坏了原来的结构。

非破坏性查找, 这种就反之了,不破坏结构。

顺序查找:

这种非常简单,就是过一下数组,一个一个的比,找到为止。

复制代码

算法系列15天速成——第四天 五大经典查找【上】

折半查找: 这种查找很有意思,就是每次都砍掉一半,

比如"幸运52“中的猜价格游戏,价格在999元以下,1分钟之内能猜到几样给几样,如果那些选手都知道折半查找,

那结果是相当的啊。

不过要注意,这种查找有两个缺点:

第一: 数组必须有序,不是有序就必须让其有序,大家也知道最快的排序也是NLogN的,所以.....呜呜。

第二: 这种查找只限于线性的顺序存储结构。

上代码:

复制代码

算法系列15天速成——第四天 五大经典查找【上】

先前也说过,查找有一种形态是破坏性的,那么对于线性结构的数据来说很悲惨,因为每次破坏一下,

可能都导致数组元素的整体前移或后移。

所以线性结构的查找不适合做破坏性操作,那么有其他的方法能解决吗?嗯,肯定有的,不过要等下一天分享。

ps: 线性查找时间复杂度:O(n);

折半无序(用快排活堆排)的时间复杂度:O(NlogN)+O(logN);

折半有序的时间复杂度:O(logN);

算法系列15天速成——第四天 五大经典查找【上】


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论