静态查找之顺序查找、折半查找、裴波那契查找、插值查找、索引顺序表查找（分块查找）

客官°小女子只卖身不卖艺 2021-09-11 04:02 435阅读 0赞

静态查找主要查找元素是否包含在查找表中，或者查找某个特定元素的属性。而动态查找需要在查找的同时插入和删除某个元素。

## **一、顺序查找** ##

对于乱序表，从表的一端逐个比较，如果相等则查找成功，如果到底还没找到，则查找不成功。在概率相等且每次都能查找成功情况下，平均查找长度为（1+2+…+n）= (N+1)/2。在概率不等情况下，如果能够优先查找那些概率高的元素显然能够提高查找效率。因此我们可以在查找前将元素先进行排序。如果概率未知，我们可以使用访问频度域，使得查找概率大的元素在查找过程中不断向优先查找的位置移动，以便下次查找时降低查找的比较次数。在考虑查找不成功情况时，平均查找长度为(1+2+…+n)/(2n)+(n+1)/2=(n+1)\*3/4。顺序查找优点是适应面广，对查找表的结构要求不够（无论有序、无序），但显然缺点是查找时间复杂度高。时间复杂度为 O(n)

## **二、折半查找** ##

基于有序表，由于表是从大到小或者从小到大排序。所以我们可以取表中间一个记录，判断查找内容在哪个区间内。一直循环直到最后low>high。折半查找比顺序查找效率高，但要求查找表有序。且由于根据下标来进行跳跃性查找，因此需要查找表顺序存储结构，如数组。链表这种就没办法有效查找。对于规模较大的有序表查找，效率较高。适合很少改动但经常查找的表。  
![这里写图片描述][20160928141214085]  
算法很简单，使用两个变量记录需要查找的区间，当mid对应的值是所需查找值时立即返回值，如果不是的话就要则显然mid对应值和查找值存在大小关系，如果大于的话，则可以将高置位赋为mid-1反之赋为mid+1。  
![这里写图片描述][20160928141224772]  
注意上图情况，最后一步时low和high邻近，这时mid刚好等于low。此时如果查找值刚好等于mid对应值，直接返回，如果大于mid对应值，则查找最后一个没有查找的位置high（这是为什么low和high相等时继续查找的原因），赋值low=high，如果小于，则赋值high=low-1，跳出循环。  
对于查找11个元素的折半查找，其查找过程可以表示成如下二叉判定树：  
![这里写图片描述][70]  
如果查找元素有n=2^h-1个，则二叉判定树的深度为h，如果查找概率相等，则折半查找的平均查找长度为：  
![这里写图片描述][70 1]  
第一层有一个节点，查找一次；第二层有2^(j-1)个节点，查找2次，以此类推。时间复杂度为log2(n)。

## **三、斐波那契查找** ##

折半查找每次将查找表对半分，裴波那契查找就是将拆分方式换成裴波那契数列。即：  
![这里写图片描述][70 2]  
F0=0  
F1=1  
F2=1  
F3=2  
F4=3  
F5=5  
.。。。  
![这里写图片描述][70 3]

## **四、插值查找** ##

线性插值法就是根据key值和下标的线性相关性，利用线性等比例性来快速定位到最有可能的位置。  
![这里写图片描述][70 4]

## **五、索引顺序表查找** ##

索引顺序表利用了无序表和有序表的特点。其索引表为有序表（按块有序），可以使用折半查找，而记录表则是块内无序的（块内无要求），不过其有个特点：后一个块内所有记录都大于前一个块内最大关键字。是对顺序查找的一种改进，这样的话首先根据索引表就能快速定位到块内，然后再在块内寻找。  
　　![这里写图片描述][20160928142028214]

## **六、总结** ##

查找算法的改进点其实都主要基于一种比较，当一个数小于比较数时，此时就没有必要再和比比较数更大的数做比较的必要性。

[有序二维数组查找][Link 1]

[20160928141214085]: /images/20210520/bbfc4f9c7b7f45a5a933a32374c1721a.png
[20160928141224772]: /images/20210520/caa95c8f61404a4f8003e054f7d1fdb9.png
[70]: /images/20210520/73d1a6cc19b9491092dd9ca7f1aad877.png
[70 1]: /images/20210520/43c2c8d1a3b64d4490a63ad6d2d98bb0.png
[70 2]: /images/20210520/c6bf72fc90ab4c8dae560a2c737e1cef.png
[70 3]: /images/20210520/e86f210bebc24974bc235974bcd69f0a.png
[70 4]: /images/20210520/782e7255c7d244a090c5adf8bdb53e50.png
[20160928142028214]: /images/20210520/441eb3c808bf4d139bdc7cf83b13fec7.png
[Link 1]: https://blog.csdn.net/qq_16234613/article/details/82261388