友情链接：数据结构专栏

查找(Searching)：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素( 或记录)。

查找表(Search Table)：是由同一类型的数据元素(或记录)构成的集合。

关键字(Key)：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。例如，在由一个学生元素构成的数据集合中，学生元素中“学号”这一数据项的值唯一地标识一名学生。

静态查找表(Static Search Table)：只作查找操作的查找表。

动态查找表(Dynamic Search Table)： 在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。

平均查找长度：在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度，则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为 A S L = ∑ i = 1 n P i C i ASL=\displaystyle\sum_{i=1}^{n} P_iC_i ASL=i=1∑n​Pi​Ci​式中， n n n是查找表的长度； P i P_i Pi​是查找第 i i i个数据元素的概率，一般认为每个数据元素的查找概率相等，即 P i = 1 / n P_i= 1/n Pi​=1/n； C i C_i Ci​是找到第 i i i个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。

顺序查找(Sequential Search) 又叫线性查找，是最基本的查找技术，作为一种最直观的查找方法，其基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置；若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。

下面给出其算法：

这种在查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但在总数据较多时，效率提高很大，是非常好的编码技巧。 上述顺序表查找时间复杂度是 O ( n ) O(n) O(n)。

折半查找(Binary Search)技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序)，线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

算法如下：

折半查找的过程可用二叉树来描述，称为判定树。 我们知道，具有n个结点的二叉树的深度为 ⌈ l o g 2 ( n + 1 ) ⌉ ⌈log_2(n+1)⌉ ⌈log2​(n+1)⌉，所以，折半查找的时间复杂度为 O ( l o g 2 n ) O(log_2n) O(log2​n)，平均情况下比顺序查找的效率高。 因为折半查找需要方便地定位查找区域，所以它要求线性表必须具有随机存取的特性。因此，该查找法仅适合于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列。

现在我们的新问题是，为什么一定要折半，而不是折四分之一或者折更多呢? 比如要在取值范围0 ~ 10000之间100个元素从小到大均匀分布的数组中查找5，我们自然会考虑从数组下标较小的开始查找。 所以，折半查找还是有改善空间的。 上述折半查找代码的第4行，等式变换后可得到： m i d = ( l o w + h i g h ) / 2 = l o w + ( h i g h − l o w ) / 2 mid=(low+high)/2 = low+(high-low)/2 mid=(low+high)/2=low+(high−low)/2也就是 m i d mid mid等于最低下标 l o w low low加上最高下标 h i g h high high与 l o w low low的差的一半。大佬们考虑的就是将这个 1 / 2 1/2 1/2进行改进，改进为下面的计算方案： m i d = l o w + ( h i g h − l o w ) { ( k e y − a [ l o w ] ) / ( a [ h i g h ] − a [ l o w ] ) } mid = low+(high-low)\{(key-a[low])/(a[high]-a[low])\} mid=low+(high−low){(key−a[low])/(a[high]−a[low])}也就是说，我们把上述折半查找代码的第4行的代码改为：

就得到了另一种有序表查找算法，插值查找法。插值查找(Interpolation Search) 是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式。应该说，从时间复杂度来看，它也是 O ( l o g 2 n ) O(log_2n) O(log2​n)，但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多。反之，数组中如果分布类似 0 , 1 , 2 , 2000 , 2001 , . . . . . . , 999998 , 99999 {0,1,2,2000,2001,......,999998, 99999} 0,1,2,2000,2001,......,999998,99999这种极端不均匀的数据，用插值查找未必是很合适的选择。

斐波那契查找(Fibonacci Search)，它是利用了黄金分割原理来实现的。

关于斐波那契数列，不了解的可点击这里做一个大致的了解

我们先定义一个斐波那契数组 F F F： 算法实现如下：

斐波那契查找算法的核心在于:

也就是说，如果要查找的记录在右侧，则左侧的数据都不用再判断了，不断反复进行下去，对处于当中的大部分数据，其工作效率要高一些，而且斐波那契查找只是最简单加减法运算，所以尽管斐波那契查找的时间复杂也为 O ( l o g n ) O(logn) O(logn)，但就平均性能来说，斐波那契查找要优于折半查找。不过如果是最坏情况，比如这里key=1，那么始终都处于左侧长半区在查找，则查找效率要低于折半查找。

现实生活中计算机要处理的数据量是极其庞大的，而数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程， 一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。 索引按照结构可以分为线性索引、树形索引和多级索引。 这里主要介绍线性索引，所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。我们重点介绍三种线性索引：稠密索引、分块索引和倒排索引。

稠密索引是很简单直白的一种索引结构。 稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项，而索引项一定是按照关键码有序的排列。如下图所示： 索引项有序也就意味着，我们要查找关键字时，可以用到折半、插值、斐波那契等有序查找算法，提高了效率。这是稠密索引优点，但是如果数据集非常大，比如上亿，那也就意味着索引也得同样的数据集长度规模，对于内存有限的计算机来说，可能就需要反复去访问磁盘，查找性能反而大大下降了。

稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。

分块有序，是把数据集的记录分成了若千块，并且这些块需要满足两个条件：

对于分块有序的数据集，将每块对应一个索引项， 这种索引方法叫做分块索引。如下图所示，我们定义的分块索引的索引项结构分三个数据项：

在分块索引表中查找，就是分两步进行: