一、查找表
1、定义
A.查找表（table）：由同一类型的数据元素（或记录）构成的集合，由于“集合”中的数据元素间存在完全松散的关系，因此查找表是非常灵便的数据结构，他是在实际应用中被大量使用的数据结构。
B.关键字（key）：元素中某个数据项的值，用于标识一个数据元素，若关键字可唯一的标识一个记录，则为“主关键字（primary key）”，若能标识若干记录，则为“次关键字（secondary key）”
C.查找：根据给定值，在查找表中确定一个其关键字 = 给定值的元素，如存在这一的记录，则查找是成功的
2、查找表的操作
A.静态查找表：查询某个“特定的”数据元素是否在查找表中，检索某个“特定的”数据元素的各种属性
B.动态查找表：在查找中同时插入查找表中不存在的元素，从查找表中删除一存在的元素
二、静态查找表
1、顺序表的查找
从表中第n个记录开始，逐个进行关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功。查找之前需要设置对r[0]的关键字赋值K，免去查找过程中每一步都要检测整个表是否查找完毕，起到了监视哨的作用，当然监视哨也可以设在高下标出。
顺序查找的缺点：平均查找长度较大，尤其当n特别大时，查找效率低。
顺序查找的优点：算法简单，适用面广，对表的结构物要求。
/* a为数组，n为要查找的数组长度，key为要查找的关键字 */
int Sequential_Search(int *a, int n, int key){
for (int i = 0; i < n; i++){
if (a[i] == key)
return i;
}
return 0;
}
//顺序查找优化(有哨兵的顺序查找)
int Sequential_Search2(int *a, int n, int key){
int i;
/* 设置a[0]为关键字值，我们称之为“哨兵” */
a[0] = key;
/* 循环从数组尾部开始 */
i = n;
while (a[i] != key){
i--;
}
/* 返回0则说明查找失败 */
return i;
}
有哨兵的顺序查找比普通查找少了一个比较（for循环中的i < n），因此在大量数据的情况下，有哨兵的顺序查找比普通顺序查找要快。
2、有序表的查找
A.折半查找：先确定待查记录所在范围（区间），然后逐步缩小范围，直到找到或找不到记录为止。
举例：05, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92有序表中中查找21和85
设指针low，hig为待查元素所在范围的下界和上界，指针mid为指示区间的中间位置，即mid = [(low + hig) / 2]，此处，low何hig的初值为1和11，即[1, 11]为待查范围。
先查找K=21：
首先r[mid].key与K比较，由于r[mid].key > K，说明若待查元素存在，必在区间[low， mid - 1]范围内，则指针hig指向第mid - 1个元素，重新求得mid = [(1 + 5) / 2] = 3
r[mid].key与K比较，由于r[mid].key < K，说明待查元素若存在，必在[mid + 1, hig]范围内，则这种low指向第mid + 1个元素，mid新值为4，比较r[mid].key与K，相等，查找成功
再看K = 85：
此时low > hig，说明没有关键字为K的元素，查找失败。
算法：
static int BinarySearch(int [] a, int n, int key) {
int low, high, mid;
low = 0;
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;
}
折半查找的效率比顺序查找高，但只适用于有序表，且为顺序存储结构，对线性链表无法进行折半查找。
B.斐波那契查找：根据斐波那契序列的特点对表进行分割
举例：有9个元素的数组array对应的斐波那契数列（长度先随便取，只要最大数大于9即可）{1, 1, 2, 3, 5, 8, 13, 21, 34}，发现大于9且最接近9的斐波那契数值是F[6] = 13，之后将数值array扩充到长度为13，末尾添加的扩充元素为原数值最后一个元素的值。mid的取值与折半查找一样，公式从(low + hig) / 2改为low + (F[k - 1] - 1)。
为什么要把数值长度阔成到F[k] - 1呢？
斐波那契的数组满足：f[k] - 1 = (f[k - 1] + f[k - 2]) - 1，这个- 1的1就是mid，如果目标在左区，数组长度缩短到f[k - 1] ，如果在右区，数组长度缩短到f[k - 2]) - 1，同样f[k - 1]) - 1 = (f[k - 2] + f[k - 3]) - 1，是一个递归的分割。
算法：
static int FibonacciSearch(int [] a, int n, int key) {
int [] F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34};
int low, high, mid, i, k;
low = 1;
high = n;
k = 0;
while (n > F[k]-1) {/* 计算n位于斐波那契数列的位置 */
k++;
}
while (low <= high) {
mid = low + F[k-1] -1;
if (key < a[mid]){
high = mid - 1;
k = k - 1;
}
else if (key > a[mid]) {
low = mid + 1;
k = k - 2;
}
else {
if (mid <= n)
return mid;
else
return n;
}
}
return 0;
}
斐波那契查找的平均性能比折半查找好，但最坏情况下的性能却比折半查找差，但是分割时只需进行加、减运算。
C.插值查找：根据给定值K来确定比较的关键字r[i].key的查找方法。
打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。
同样的，比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5， 我们自然会考虑从数组下标较小的开始查找。
经过以上分析，折半查找这种查找方式，还是有改进空间的，并不一定是折半的。
j将这个1 / 2进行改进，成为
改成这样有什么道理呢？假设a[11] = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99}，low = 1，high = 10，则a[low] = 1，a[high] = 99，如果我们要找的是key = 16时，按原来的折半查找的做法，我们需要四次才可以得到结果，但如果使用新办法，
即mid ≈ 1 + 0.153*(10 - 1) = 2.377取整得到mid = 2，我们只需要两次查找到结果了，显著大大提高了查找的效率。
换句话说，我们只需要在折半查找算法更改一行代码就可以实现插值算法了。
mid=low+(high-low)*(key-a[low])/(a[high]-a[low]); //插值
插值查找适用于关键字均匀分布的表，在这种情况下，对n值较大的顺序表，他的平均性能比折半查找好。
