线性表的查找
顺序查找
技巧：设置哨兵，放在下标为0的位置。
int Search_Seq(SSTable ST, KeyType key) {
ST.R[0].key = key;
for(int i = ST.length; ST.R[i].key != key; i--);
return i;
}
算法分析
适用于顺序结构和链式结构，不要求记录按关键字有序。
平均查找长度为(n + 1) / 2，查找效率低。
折半（二分）查找
int Search_Bin(SSTable ST, KeyType key) {
low = 1; high = ST.length;
while(low <= high) {
mid = (low + right) / 2;
if(key == ST.R[mid].key) return mid;
else if(key < ST.R[mid].key) high = mid - 1;
else low = mid + 1;
}
return 0;
}
二叉判定树
当前查找区间的中间位置是根，左子树和右子树分别是左子表和右子表。
则查找失败就是走了一条从根结点到外部结点的路径，比较的关键字个数等于路径上的内部结点个数。
当n较大时，ASL = log2(n + 1) - 1
算法分析
要求必须是顺序存储结构，且按关键字有序排列。
对于长度为n的有序表，需要比较的关键字个数最多是floor(log2(n)) + 1。时间复杂度为O(log2(n)).
分块查找（索引顺序查找）
建立一个索引表，按关键字有序，整个待查找表有序或者分块有序。
确定块的查找可以用顺序查找或者折半查找，块中的查找只能用顺序查找（因为不一定关键字有序）。
算法分析
顺序查找：ASL = (1 / 2) * (n / s + s) + 1
折半查找：ASL = log2(n / s + 1) + (s / 2)
便于插入和删除，可以实现在快速查找的同时经常动态变化。