算法快学笔记（十八）：史上最全查找算法总结

女爷i 2023-06-13 09:21 61阅读 0赞

# 1. 简介 #

查找算是工作过程中运用最广泛的操作了，操作系统读取文件时需要查找，从数据库读取数据时需要查找…

本文将对常见的查找算法进行总结。

# 2. 常见算法 #

## 2.1 顺序查找 ##

基本思想：

该算法简单粗暴，从头（或是最后）开始遍历，找到要查的数据就停止遍历并返回结果，如果遍历完也没有找到就是查找不成功。

时间复杂度:O(n)

## 2.2 有序表 ##

### 2.2.1 二分查找 ###

基本思想：

1.  将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
2.  否则利用中间位置记录将表分成前、后两个子表，
    
    1.  如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，
    2.  否则进一步查找后一子表。
3.  重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功

时间复杂度:O(log2n)

### 2.2.2 插值查找 ###

对于数值变化幅度比较均匀的有序数组，要查的值在数组中的位置基本是可以确定的，例如\[10,20,30,40,60,70,80,90,100,120,130,140\]这个数组，30是在数组的前半部分，60应该是离30不远的位置，而130则是在数组的后半部分，120,140是在130附近。

二分查找法用在上面的数组中，对于位置的计算可能就存在优化的空间了，优化后的算法就叫插值查找法。

基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，改进后的公式如下：

![在这里插入图片描述][20191115115447586.jpg]

时间复杂度：o(logn)

适用场景：对于表长较大而关键字分布比较均匀的查找表来说，效率高于二分查找法。

### 2.2.3 斐波那契查找 ###

斐波那契数列如下所示：

![在这里插入图片描述][20191115115531891.jpg]

斐波那契查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1（F代表斐波那契数列），如下图所示：  
![在这里插入图片描述][20191115115547325.jpg]

基本思想：

由斐波那契数列 F\[k\]=F\[k-1\]+F\[k-2\]的性质，可以得到（F\[k\]-1）=（F\[k-1\]-1）+（F\[k-2\]-1）+1。该式说明：只要顺序表的长度为F\[k\]-1，则可以将该表分成长度为F\[k-1\]-1和F\[k-2\]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1

但顺序表长度n不一定刚好等于F\[k\]-1，所以需要将原来的顺序表长度n增加至F\[k\]-1。这里的k值只要能使得F\[k\]-1恰好大于或等于n即可。

时间复杂度：O(log2n)。

理轮上，由于下述原因，该算法的平均性能会高于二分查找法：

1.  如果查找的记录在右侧，则查找的数据量会少一些
2.  mid=low+F(k-1)-1. 是基于加减法的操作，数据量大的时候，效率上会高于除法。

## 2.3 无序数据 ##

数据按照时间存储，值可能是无序的。

### 2.3.1 简单索引 ###

基本思想：存储数据的时候，使用数据的key创建出有序的索引，索引中还保存指向原始数据的指针。查找的时候可以用有序表的算法找到索引，然后用索引中存储的数据指针找到原始数据。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]

### 2.3.2 分块索引 ###

数据量大的时候，简单索引需要较多的内存空间去存储索引数据，此时可以考虑使用分块索引。

算法思想：将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……

索引结果如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 1]

查找流程：

1.  先选取各块中的最大关键字构成一个索引表；
2.  查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。

### 2.3.3 倒排索引 ###

解决文本搜索的必备技能，请参考：https://blog.csdn.net/eric\_sunah/article/details/79404022 第五章节

### 2.3.4 哈希查找 ###

请参考：https://blog.csdn.net/eric\_sunah/article/details/85393235

### 2.3.5 B家族的树 ###

曾转过一篇关于常见B系列树的介绍，包括：B树、B-树、B+树、B\*树，请参考：https://blog.csdn.net/eric\_sunah/article/details/86482113

### 2.3.6 红黑树查找 ###

请参考：https://blog.csdn.net/eric\_sunah/article/details/86482146

[20191115115447586.jpg]: https://img-blog.csdnimg.cn/20191115115447586.jpg
[20191115115531891.jpg]: https://img-blog.csdnimg.cn/20191115115531891.jpg
[20191115115547325.jpg]: https://img-blog.csdnimg.cn/20191115115547325.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191115115610621.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191115115622282.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY=,size_16,color_FFFFFF,t_70