一:概论
查找,或搜索(Search),是最频繁的操作,基础中的基础.
查找表(search table):也就是指在一个容器中查找目标内容,所有的内容(数据元素)构成的集合就是查找表.
关键字(key):key这里是指数据元素的某个数据项(字段)的值,键值,而不是字段本身,它可能唯一的标识着一个元素,叫做主关键字,也就是每一条数据的主关键字都不相同,而这个值对应的字段就是主键.
静态查找表:只做查找操作
动态查找表:查找,插入,删除操作
查找是从集合中找到目标数据,一般来说,集合中的数据直接并没什么关系,比如一个普通的订单表,每条数据之间没有相关性,但是想要提升查找的性能,就需要把集合组织成表,树等结构,利用数据结构的特性来提升查找效率.
二:顺序表查找
如果你想从一堆散乱堆砌的书中找到一本想要的书,这是你会考虑先把这堆书排列整齐,然后从第一本按顺序查找.
这个过程就是把集合组织成线性表,然后从线性表的第一个元素开始对比,叫做顺序查找,是最基本的查找方式.
如果用代码实现,那就是遍历线性表
遍历
当然也可以优化一下,不使用for循环遍历,省去每次对比i是否<=n的过程
返回0则查找失败
显然顺序表查找的复杂度O(n).
三:有序表查找
还是找书的例子,如果随便把书摆在书架上,那么查找只能从第一本开始,如果按照书名首字拼音来摆好,那么直接跳到对应的位置开始找就行了
这就是对集合根据一个或多个key来进行有序排列,组织成一个有序的线性表.
1.二分查找
二分查找,或者折半查找,很容易理解,首先要是有序线性表.
比如在[0,1,16,24,35,47,59,62,73,88,99]中查找62,这是个简化的例子,这些数字是复杂数据的一个关键字,它的意义在于找到62然后访问这条数据的具体信息.
在下面的例子中,都不考虑下标0,0的位置放一个数值0,最小下标从1开始
代码实现如下,low和high表示当前要查找的范围,也就是记录折半折到哪了,注释基本写的很详细.
代码
过程很好理解关键是复杂度的分析,把二分查找绘制成二叉树,发现这个例子中的查找,就是其中一条路径,根据n个节点的完全二叉树深度是log₂n + 1,那么二分查找的复杂度就是O(logn).
image.png
2.插值查找
回到找书的例子,在把书按顺序摆好之后,二分法就没必要了,如果是找博物杂志,你会知道在靠前的位置,如果是找赵氏孤儿,你会知道到靠后的位置找,如果转换成数学问题,那就类似于从0-10000中找88和9900.
插值查找其实只需要把二分查找稍微改变一下就行.
这里需要用到插值公式mid = low + (key - a[low]) / (a[high] - a[low]) * (high - low),这是个数学问题,归纳自上面讲到的例子,从每次取中间作为mid,变成按照比例来计算mid,原先mid先=5,现在mid先=2(取整),发现a[2]就是16,直接就找到了
image.png
从时间复杂度来看,差值查找也是O(n),属于是对二分查找的优化.
3.斐波那契查找
斐波那契查找也类似于插值查找,是利用斐波那契数列;
斐波那契数列
算法代码:
代码
分析:
数组a=[0,1,1,16,24,35,47,59,62,73,88,99],需要查找是值是59,数组F是斐波那契数列;
两个指针low和high,从0和n开始,第6~8行,得到k= 7;
第9~10行是为了补全数组,后面有用;
第13行,mid = 1+F[7-1]-1 = 8,也就是从下标8开始;
此时key = 59,a[8] = 63,16~17行得到high = 7;key = 6;
几次循环
经过几次循环得到a[6] = key;
当key<a[mid]时,新的查找范围是low到mid-1,此时范围内个数是F[k-1]-1个,
当k>a[mid]时,新的查找范围是mid到high,个数是F[k-2]-1个;
image.png
斐波那契查找的复杂度也是O(nlogn),但是对于处在中间的大部分数据,效率比插值查找更高;
另外斐波那契查找仅需要加法运算,折半和插值需要四则运算,对于巨量的数据来说,效率也有提升.
网友评论