一、查找表
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：

image.png

首先r[mid].key与K比较，由于r[mid].key > K，说明若待查元素存在，必在区间[low， mid - 1]范围内，则指针hig指向第mid - 1个元素，重新求得mid = [(1 + 5) / 2] = 3

image.png

image.png

image.png

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， 我们自然会考虑从数组下标较小的开始查找。
经过以上分析，折半查找这种查找方式，还是有改进空间的，并不一定是折半的。

image.png

image.png

image.png

即mid ≈ 1 + 0.153*(10 - 1) = 2.377取整得到mid = 2，我们只需要两次查找到结果了，显著大大提高了查找的效率。
换句话说，我们只需要在折半查找算法更改一行代码就可以实现插值算法了。

mid=low+(high-low)*(key-a[low])/(a[high]-a[low]); //插值

插值查找适用于关键字均匀分布的表，在这种情况下，对n值较大的顺序表，他的平均性能比折半查找好。