在我们的生活中,无处不存在着查找,比如找一下班里哪个mm最pl,猜一猜mm的芳龄.......对的这些都是查找。
在我们的算法中,有一种叫做线性查找。
分为:顺序查找。
折半查找。
查找有两种形态:
分为:破坏性查找, 比如有一群mm,我猜她们的年龄,第一位猜到了是23+,此时这位mm已经从我脑海里面的mmlist中remove掉了。
哥不找23+的,所以此种查找破坏了原来的结构。
非破坏性查找, 这种就反之了,不破坏结构。
顺序查找:
这种非常简单,就是过一下数组,一个一个的比,找到为止。
折半查找: 这种查找很有意思,就是每次都砍掉一半,
比如"幸运52“中的猜价格游戏,价格在999元以下,1分钟之内能猜到几样给几样,如果那些选手都知道折半查找,
那结果是相当的啊。
不过要注意,这种查找有两个缺点:
第一: 数组必须有序,不是有序就必须让其有序,大家也知道最快的排序也是NLogN的,所以.....呜呜。
第二: 这种查找只限于线性的顺序存储结构。
上代码:
先前也说过,查找有一种形态是破坏性的,那么对于线性结构的数据来说很悲惨,因为每次破坏一下,
可能都导致数组元素的整体前移或后移。
所以线性结构的查找不适合做破坏性操作,那么有其他的方法能解决吗?嗯,肯定有的,不过要等下一天分享。
ps: 线性查找时间复杂度:O(n);
折半无序(用快排活堆排)的时间复杂度:O(NlogN)+O(logN);
折半有序的时间复杂度:O(logN);
分享到:
相关推荐
算法系列15天速成——第四天-五大经典查找【上】 五大常用算法
算法系列15天速成——第六天-五大经典查找【下】,算法数据结构 五大常用算法
算法系列15天速成——第五天-五大经典查找【中】,算法数据结构 五大常用算法
五大经典查找【下】 算法系列15天速成——第五天 五大经典查找【中】 算法系列15天速成——第四天 五大经典查找【上】 算法系列15天速成——第三天 七大经典排序【下】 算法系列15天速成——第二天 七大经典排序【中...
算法系列15天速成 数据结构 算法 树、图、堆栈、队列
计算机系的教材,算法导论————————————————————————————————
今天是大结局,说下“图”的最后一点东西,“最小生成树“和”最短路径
今天说下最后一种树,大家可否知道,文件压缩程序里面的核心结构,核心算法是什么?或许你知道,他就运用了赫夫曼树
五大常用算法——回溯算法详解及经典例题,算法数据结构 五大常用算法
五大常用算法——分支限界算法详解及经典例题,算法数据结构 五大常用算法
五大常用算法——动态规划算法详解及经典例题,算法数据结构 五大常用算法
代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码 基于遗传算法的优化计算——建模自变量降维代码代码...
思维进化算法优化BP神经网络——非线性函数拟合.zip
垃圾回收GC经典算法(csdn)————程序
深大算法实验五——查找所有的桥
算法模板.doc————电子版_doc版
算法之NlogN排序算法(csdn)————程序
简单的算法举例(csdn)————程序
在我们的生活中,无处不存在着查找,比如找一下班里哪个mm最pl,猜一猜mm的芳龄....... 对的这些都是查找
MIT算法导论——算法顶尖经典教材MIT算法导论——算法顶尖经典教材MIT算法导论——算法顶尖经典教材MIT算法导论——算法顶尖经典教材MIT算法导论——算法顶尖经典教材