本文主要介绍数据结构中的查找算法，主要介绍顺序查找、折半查找（二分查找）、树表查找、分块查找、哈希查找（散列）。 其他的一些查找算法也会有所介绍。

查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。

查找表按照操作方式可分为：

**平均查找长度（Average Search Length，ASL）：**在所有的查找过程中进行关键字的比较次数的平均值。 对于含有n个数据元素的查找表，查找成功的平均查找长度计算公式如下： A S L = ∑ i = 1 n P i C i ASL = \sum_{i=1}^{n}P_{i}C_{i} ASL=i=1∑n​Pi​Ci​ 　　 P i P_i Pi​：查找表中第i个数据元素的概率,一般等概率为 1 n \frac{1}{n} n1​ 　　 C i ​ C_i​ Ci​​：找到第i个数据元素时已经比较过的次数。

算法简介 顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。时间复杂度为 O （ n ） O（n） O（n）。

基本思路

从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。

优缺点

算法实现

注意： 折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

算法实现

算法简介 在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？ 打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。 经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：　 m i d = ( l o w + h i g h ) / 2 , 即 m i d = l o w + 1 / 2 ( h i g h − l o w ) mid=(low+high)/2, 即mid=low+1/2(high-low) mid=(low+high)/2,即mid=low+1/2(high−low) 通过类比，我们可以将查找的点改进为如下： 　　 mid=low+(key-a[low])/(a[high]-a[low])*(high-low)， 也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。 查找成功或者失败的时间复杂度均为 O ( l o g 2 ( l o g 2 n ) ) O(log_2(log_2^n)) O(log2​(log2n​)),最坏情况可能需要 O （ n ） O（n） O（n）。 　 算法思想 基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，插值查找也属于有序查找。 注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

算法实现

算法简介 要求是顺序表，分块查找又称索引顺序查找，它是顺序查找的一种改进方法。 时间复杂度： O ( l o g ( m ) + n / m ) O(log(m)+n/m) O(log(m)+n/m)

算法思想

算法流程

平均查找长度 将长度为n的查找表均匀分为m块，每块有s个记录，在等概率的情况，平均查找长度计算如下：

索引和块内均用顺序查找 A S L = m + 1 2 + s + 1 2 = s 2 + 2 s + n 2 s , ( m s = n ) ASL= \frac{m+1}{2} + \frac{s+1}{2} = \frac{s^2+2s+n}{2s},(ms=n) ASL=2m+1​+2s+1​=2ss2+2s+n​,(ms=n) 特殊的 当 s = n 时 ， A S L m i n = n + 1 当 s =\sqrt{n}时，ASL_{min} = \sqrt{n}+1 当s=n ​时，ASLmin​=n ​+1

索引折半查找，块内顺序查找

A S L = ⌈ l o g 2 ( m + 1 ) ⌉ + s + 1 2 ASL = \left \lceil log_2^{(m+1)} \right \rceil + \frac{s+1}{2} ASL=⌈log2(m+1)​⌉+2s+1​

这部分大致知道过程，先记录下来，以后有时间在认真研究一下=-=，主要参考百度百科

算法简介 斐波那契数列，又称黄金分割数列，指的是这样一个数列： 1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 ⋅ ⋅ ⋅ ⋅ 1、1、2、3、5、8、13、21、···· 1、1、2、3、5、8、13、21、⋅⋅⋅⋅，在数学上，斐波那契被递归方法如下定义： F ( 1 ) = 1 ， F ( 2 ) = 1 ， F ( n ) = f ( n − 1 ) + F ( n − 2 ) （ n ; = 2 ） F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n;=2） F(1)=1，F(2)=1，F(n)=f(n−1)+F(n−2)（n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。

斐波那契查找的时间复杂度还是 O ( l o g 2 n ) O(log_2^n ) O(log2n​)，但是与折半查找相比，斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间，因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定。

算法思想 也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。 相对于折半查找，一般将待比较的key值与第 m i d = （ l o w + h i g h / 2 mid=（low+high/2 mid=（low+high/2位置的元素比较，比较结果分三种情况：

斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。要求开始表中记录的个数为某个斐波那契数小1，及 n = F ( k ) − 1 n=F(k)-1 n=F(k)−1;

开始将k值与第 F ( k − 1 ) F(k-1) F(k−1)位置的记录进行比较(及 m i d = l o w + F ( k − 1 ) − 1 mid=low+F(k-1)-1 mid=low+F(k−1)−1),比较结果也分为三种

说明： l o w = m i d + 1 low=mid+1 low=mid+1说明待查找的元素在 [ m i d + 1 , h i g h ] [mid+1,high] [mid+1,high]范围内， k − = 2 k-=2 k−=2 说明范围 [ m i d + 1 , h i g h ] [mid+1,high] [mid+1,high]内的元素个数为 n − ( F ( k − 1 ) ) = F ( k ) − 1 − F ( k − 1 ) = F ( k ) − F ( k − 1 ) − 1 = F ( k − 2 ) − 1 n-(F(k-1))= F(k)-1-F(k-1)=F(k)-F(k-1)-1=F(k-2)-1 n−(F(k−1))=F(k)−1−F(k−1)=F(k)−F(k−1)−1=F(k−2)−1个，所以可以递归的应用斐波那契查找。

说明： l o w = m i d + 1 low=mid+1 low=mid+1说明待查找的元素在 [ l o w , m i d − 1 ] [low,mid-1] [low,mid−1]范围内， k − = 1 k-=1 k−=1 说明范围 [ l o w , m i d − 1 ] [low,mid-1] [low,mid−1]内的元素个数为 F ( k − 1 ) − 1 F(k-1)-1 F(k−1)−1个，所以可以递归 的应用斐波那契查找。 　　 n = F ( k ) − 1 n=F(k)-1 n=F(k)−1， 表中记录的个数为某个斐波那契数小1。这是为什么呢？

是为了格式上的统一，以方便递归或者循环程序的编写。表中的数据是 F ( k ) − 1 F(k)-1 F(k)−1个，使用 m i d mid mid值进行分割又用掉一个，那么剩下 F ( k ) − 2 F(k)-2 F(k)−2个。正好分给两个子序列，每个子序列的个数分别是 F ( k − 1 ) − 1 F(k-1)-1 F(k−1)−1与 F ( k − 2 ) − 1 F(k-2)-1 F(k−2)−1个，格式上与之前是统一的。不然的话，每个子序列的元素个数有可能是 F ( k − 1 ) ， F ( k − 1 ) − 1 ， F ( k − 2 ) ， F ( k − 2 ) − 1 F(k-1)，F(k-1)-1，F(k-2)，F(k-2)-1 F(k−1)，F(k−1)−1，F(k−2)，F(k−2)−1个，写程序会非常麻烦。

算法举例 对于斐波那契数列： 1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 34 、 55 、 89 … … 1、1、2、3、5、8、13、21、34、55、89…… 1、1、2、3、5、8、13、21、34、55、89……（也可以从0开始），前后两个数字的比值随着数列的增加，越来越接近黄金比值0.618。比如这里的89，把它想象成整个有序表的元素个数，而89是由前面的两个斐波那契数34和55相加之后的和，也就是说把元素个数为89的有序表分成由前55个数据元素组成的前半段和由后34个数据元素组成的后半段，那么前半段元素个数和整个有序表长度的比值就接近黄金比值0.618，假如要查找的元素在前半段，那么继续按照斐波那契数列来看，55 = 34 + 21，所以继续把前半段分成前34个数据元素的前半段和后21个元素的后半段，继续查找，如此反复，直到查找成功或失败，这样就把斐波那契数列应用到查找算法中了。

从图中可以看出，当有序表的元素个数不是斐波那契数列中的某个数字时，需要把有序表的元素个数长度补齐，让它成为斐波那契数列中的一个数值，当然把原有序表截断肯定是不可能的，不然还怎么查找。然后图中标识每次取斐波那契数列中的某个值时(F[k])，都会进行-1操作，这是因为有序表数组位序从0开始的，纯粹是为了迎合位序从0开始。

算法实现