查找的基本概念
查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合。
关键字（key）是数据元素中某个数据项的值，又称为键值，用它可以标识一个数据元素。若此关键字可以唯一标识一个记录，则称此关键字为主关键字（Primary Key）。
对应那些可以识别多个数据元素（或记录）的关键字，我们称为次关键字。
查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值得数据元素（或记录）。
静态查找表：只做查找操作的查找表。它的主要操作有：
（1）查询某个“特定的”数据元素是否在查找表中。
（2）检索某个“特定的”数据元素和各种属性。
动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。主要有两个：
（1）查找时插入数据元素
（2）查找时删除数据元素
顺序查找
顺序查找又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果知道最后一个（或第一个）记录，其关键字和给定值比较都不相等时，则表中没有所查的记录，查找不成功。
顺序查找算法实现：
int Sequential_Search(int *a,int n,int key){
int i;
for(i=1;i<=n;i++){
if(a[i]==key)
return i;
}
return 0;
}
上述代码并非足够完美，因为每次循环时都需要对i是否越界，即是否小于等于n作判断。改进方法是设置一个哨兵，可以解决不需要每次让i与n作比较：
int Sequential_Search2(int *a,int n,int key){
int i;
a[0]=key; //设置a[0]为关键值 我们称之为哨兵
i=n; //循环从数据尾部开始
while(a[i]!=key){
i--;
}
return i; //返回0则说明查找失败
}
对于这种顺序表查找算法来说，查找成功最好的情况就是在第一个位置就找到了，算法时间复杂度为O(1)，最坏的情况是在最后一个位置才找到，需要n次比较，时间复杂度为O(n)，当查找不成功时，需要n+1次比较，时间复杂度为O(n)。关键字在任何已位置的概率相同，所以平均查找次数为(n+1)/2，所以最终时间复杂度为O(n)。
折半查找
折半查找技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是：有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
int Binary_Search(int *a,int n,int key){
int low,high,mid;
low=1; //定义最低下标为记录首位
high=n; //定义最高下标为记录末位
while(low<=high){
mid=(low+high)/2; //折半
if(key<a[mid])
high=mid-1; //最高下标调整到中位下标小一位
else if(key>a[mid])
low=mid+1; //最低下标调整到中位下标大一位
else
return mid;
}
return 0;
}
我们可以将这个数组查找过程绘制成一颗二叉树：
根据二叉树的性质，具有n个结点的完全二叉树的深度为[log2n]+1，因此最终折半查找算法的时间复杂度为O(logn)，它显然远远好于顺序查找的O(n)。
插值查找
现在我们的新问题是，为什么一定要折半，而不是折四分之一或者这更多查找呢？
折半查找公式为：
也就是mid等于最低下标low加上最高下标high与low的差的一半。我们考虑的就是将这个1/2进行改进：
插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式：
从时间复杂度来看，它也是O(logn)，但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多。反之，数组中如果分布类似{0,1,2,2000,2001,….,999998,999999}这种极端不均匀的数据，用插值查找未必是很合适的选择。
线性索引查找
数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构造，每个索引项至少应该包含关键字和其对应的记录在存储器中的位置等信息。
索引按照结构可以分为线性索引、树型索引和多级索引。
所谓的线性索引就是将索引项集合组织为线性结构，也称为索引表。
稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项，如图所示：
对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。索引项有序也就意味着，我们查找关键字时，可以用到折半、插值等有序查找算法，大大提高效率，这是稠密索引优点。但是如果数据集非常大，比如上亿，那也就意味着索引也得到同样的数据集长度规模，对于内存有限的计算机来说，可能就需要反复去访问磁盘，查找性能反而大大下降了。
分块索引
稠密索引因为索引与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。
分块有序，就是把数据集的记录分成若干块，并且这些块需要满足两个条件：
块内无序，即每一块内的记录不要求有序，当然，如果能够让块内有序对查找来说更理想，不过这就要付出大量时间和空间的代价，因此通常不要求块内有序。
块间有序，要求第二块所有记录的关键字均大于第一块记录中的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字…..因为只有块间有序，才有可能在查找时带来效率。
对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引，定义的分块索引项结构分为三个数据项：
1、最大关键码，它存储每一块中最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大；
2、存储了块中的记录个数，以便于循环时使用；
3、用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。
在分块索引表中查找，就是分两步进行：
1、在分块索引表中查找要查关键字所在的块，由于分块索引表是块间有序的，因此很容易利用折半、插值等算法得到结果。
2、根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序，因此只能顺序查找。
倒排索引
倒排索引算是最基础的搜索技术。现在有两篇极短的英文文章，编号为1和2。
1.Books and friends should be few but good.
2.A good book is a good friend.
假设我们忽略掉如books、friends中的复数s以及如A这样的大小写差异。我们可以整理出这样一张单词表，并将单词做了排序，也就是表格显示了每个不同的单词分别出现在哪篇文章中，比如“good”它在两篇文章中都有出现，而is只是在文章2中才有：
有了这样一张单词表，我们要搜索文章，就非常方便了。如果你在搜索框中填写book关键字。系统就先在这张单词表中有序查找book，找到后就将它对应的文章编号1和2的文章地址（通常在搜索引擎中就是网页的标题和链接）返回，并告诉你，查找到两条记录，用时0.0001秒。由于单词表是有序的，查找效率很高，返回的又只是文章的编号，所以整体速度都非常快。
如果没有这张单词表，为了能证实所有文章中有还是没有关键字book，则需要对每一篇文章每一个单词顺序查找。在文章数海量的情况下，这样的做法只存在理论上可行性，现实中是没有愿意使用的。
单词表就是索引表，索引项的通用结构是：
次关键码，例如上面的“英文单词”；
记录号表，例如上面的“文章编号”；
其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）。这样的索引方法就是倒排索引。倒排索引源于实际应用中需要根据属性（或字段、次关键码）的值来查找记录。这种索引表中的每一项都包含一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。
倒排索引的优点显然就是查找记录非常快，基本等于生成索引表后，查找时都不用去读取记录，就可以得到结果。但它的缺点是这个记录号不定长。若是对多篇文章所有单词建立倒排索引，那每个单词都将对应相当多的文章编号，维护比较困难，插入和删除操作都需要作相应的处理。