Static Search Table
静态查找表可以有不同的表示方法，在不同的表示方法中，实现查找操作的方法也不同。
先介绍关于平均查找长度ASL(Average Search Length)的概念。
【平均查找长度的定义】为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。
对于含有n个记录的表，查找成功时的平均查找长度为，其中：
为查找表中第i个记录的概率
；
为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行比较过的关键字个数。显然，
随查找过程的不同而不同。
顺序表的查找
顺序查找(Sequential Search)的查找过程：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。
【监视哨】在查找之前，要先对ST.elem[0]的关键字赋值key，目的在于免去查找过程中每一步都要检测整个表是否查找完毕。在此，ST.elem[0]起到了监视哨的作用。这仅是一个程序设计技巧上的改进，然而实践证明，这个改进能使顺序查找在ST.length>=1000时，进行一次查找所需的平均时间几乎减少一半。当然，监视哨也可以设在高下标处。
【顺序查找的平均查找长度】(假设每个记录的查找的概率相等，且)
假设查找成功与不成功的可能性相同，对每个记录的查找概率也相等，则P_i = 1 / (2n)，此时顺序查找的平均查找长度为
有序表查找
有序表表示静态链表时，有下面三种查找方法：
- 折半查找
- 斐波纳契查找
- 插值查找
折半查找
折半查找(Binary Search)的查找过程：先确定待查记录所在的范围(区间)，然后逐步缩小范围直到找到或找不到该记录为止。
【确定中间值mid的计算公式】假设low和high分别指示待查元素所在范围的下界和上界，指针mid指示区域的中间位置，即。
折半查找过程是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或查找区间的大小小于零时(表示查找不成功)为止。
折半查找算法的相应代码在文末。
【折半查找的平均查找长度】(假设每个记录的查找的概率相等，且)
对任意的n，当n较大(n>50)时，可有下列近似结果:
可见，折半查找的效率比顺序查找高，但折半查找只适用于有序表，且限于顺序存储结构(对线性链表无法有效地进行折半查找)。
斐波那契查找
根据斐波那契序列的特点进行分割。详细介绍点击链接跳转
斐波那契查找的平均性能比折半查找要好，但最坏情况下的性能(仍然是O(logn))却比折半查找差。它还有一个优点就是分割时只需进行加、减运算。
插值查找
插值查找是根据给定值key来确定进行比较的关键字ST.elem[i].key的查找方法。令，其中ST.elem[l]和ST.elem[h]分别为有序表中具有最小关键字和最大关键字的记录。
显然，这种插值查找只适用于关键字均匀分布的表，在这种情况下，对表长较大的顺序表，其平均性能比折半查找好。
静态树表的查找
上一部分中，对有序表地查找性能的讨论是在“等概率”的前提下进行的，下面考虑“不等概率”的情况下。
【静态最优查找树】Static Optimal Search Tree。查找性能达最佳的判定树是其带权内路径长度之和PH值取最小值的二叉树。其中n为二叉树上的结点个数(即有序表的长度)，
h_i为第i个结点在二叉树上的层次数；结点的权w_i = c * p_i，其中p_i是结点的查找概率，c为某个常量。称PH值取最小的二叉树为静态最优查找树(Static Optimal Search Tree)。
【次优查找树】Nearly Optimal Search Tree。构造一棵二叉树，使这棵二叉树的带权内路径长度PH值在所有具有同样权值的二叉树中近似为最小，称此类二叉树为次优查找树。
给一篇次优二叉树详细图解博客，写的实在ok！
构造递归次优查找树的递归算法本博客文末。
索引顺序表的查找
若以索引顺序表表示静态查找表，则search函数可用分块查找来实现。
分块查找又称为索引顺序查找，是顺序查找的一种改进方法。此查找法中，除表本身以外，尚需建立一个“索引表”。如下图：
上图中，表中含有18个记录，可分为3个子表(R1,R2,…,R6)、(R7,R8,…,R12)、(R13,R14,…,R18)。
对每个子表(或称块)建立一个索引项，其中包括两项内容：关键字项(其值为该子表内的最大关键字)和指针项(指示该子表的第一个记录在表中的位置)。索引表按关键字有序，则表或者有序或者分块有序。
所谓“分块有序”指的是第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中的所有关键字都大于第二个子表中的最大关键字，……，依次类推。
分块查找过程分为两步进行：
- 先确定待查记录所在的块(子表)；
- 在块中顺序查找。
我们使用上图，然后举例子来说明具体操作步骤。假设给定值key=38,则先将key依次和索引表中各最大关键字进行比较，因为
22<key<48，则关键字为38的记录若存在，必定在第二个子表中，由于同一个索引项中的指针指示第二个子表中的第一个记录是表中第7个记录，则自第7个记录起进行顺序查找，直到ST.elem[10].key=key为止。假如此子表中没有关键字等于key的记录(例如key=29)时，自第7个记录起至第12个记录的关键字和key比较都不等)，则查找不成功。
由于索引项组成的索引表按关键字有序，则确定块的查找可以用顺序查找，亦可以用折半查找，而块中记录是任意排列的，则在块中只能是顺序查找。故而，分块查找的算法即为这两种查找算法的简单合成。
分块查找的平均查找长度为，其中Lb为查找索引表确定所在块的平均查找长度，Lw是在块中查找元素的平均查找长度。
一般情况下，为进行分块查找，可以将长度为n的表均匀分为b块，每块含有s个记录，即；有假定表中每个记录的查找记录概率相等，则每块查找的概率为1/b，块中每个记录的查找概率为1/s。
若用顺序查找确定所在块，则分块查找的平均查找长度为
可见，此时的平均查找长度不仅和表长n有关，而且和每一块中的记录个数s有关。再给定n的前提下，s是可以选择的。容易证明，当s=n^0.5时，ASL_{bs}取最小值
n^0.5+1。这个值比顺序查找有了很大改进，但远远不及折半查找。
若用折半查找确定所在块，则分块查找的平均查找长度为
代码
【折半查找算法】
int Search_Bin(SSTable ST, KeyType key) {
// 在有序表ST中折半查找其关键字等于key的数据元素
// 若找到，则函数值为该元素值在该表中的位置，否则为0
low = 1; high = ST.length; // 置区间初值
while (low < high) {
mid = (low + high) / 2;
if (EQ(key, ST.elem[mid].key)) return mid; // 找到待查元素
else if (LT(key, ST.elem[mid].key)) high = mid - 1; // 继续在前半区间进行查找
else low = mid + 1; // 继续在后半区间进行查找
}
return 0; // 顺序表中不存在待查元素
}
数组下标从1开始，函数体末尾的
return 0;相呼应，太美妙了！
【构造次优查找树的递归算法】
void SecondOptimal(BiTree &T, ElemType R[], float sw[], int low, int high) {
// 由有序表R[low...high]及其累积权值表sw(其中sw[0]==0)递归构造次优查找树
i = low; min = abs(sw[high] - sw[low]); dw = sw[high] + sw[low - 1];
for(j = low + 1; j <= high; ++j) // 选择最小的P_i值
if(abs(dw - sw[j] - sw[j - 1]) < min) {
i = j; min = abs(dw - sw[j] - sw[j - 1]);
}
T = (BiTree) malloc (sizeof(BiTNode));
T->data = R[i]; // 生成结点
if(i == low) T->lchild = NULL; // 左子树空
else SecondOptimal(T->lchild, R, sw, low, i - 1); // 构造左子树
if(i == high) T->rchild = NULL; // 右子树空
else SecondOptimal(T->rchild, R, sw, i + 1, high); // 构造右子树
}