顺序查找和折半查找

顺序查找

哨兵

将查找表的第一个元素设置为待查找的元素，将关键字匹配和数组越界的比较合一，可以减少比较次数。

/** 
 * 返回 0，说明遇到哨兵，查找失败
 * 返回 >0，查找成功
 */
function(SearchTable table, Key key) {
    table[0] = key;
    // 从后往前找
    for (i = table.size(); table[i] != key; --i);
    return i;
}

有序线性表的查找

有序线性表的查找过程对应的「判定树」为：

其中：

• 「圆形节点」表示线性表中存在的元素
• 「矩形节点」表示失败节点，可以报告错误信息

注：有序线性表和无序线性表，如果查找成功，两者的平均查找次数是相同的；如果查找不成功，有序线性表的平均查找次数更少。

折半查找

只能用于有序顺序表

平均查找长度为（记一下这个结论）：

折半查找的过程对应的「判定树」为：（左右子树的节点数量不超过 1，仅考虑圆形节点）

注：区别「折半查找」和「二叉排序树」的查找。「二叉排序树」的树形可能不是平衡的，极端情况是「单支树」；而「折半查找」对应的判定树是平衡的。

折半查找的判定树，在画的时候需要有一致的「取整方法」：

分块查找

为什么要有分块查找

折半查找已经非常高效了，为什么还要有分块查找？
因为折半查找是一个「静态」的结构，增删数据时开销较大；
「分块查找」的结构是一个折中，增删数据时开销不会很大，查找速度也不会很慢。

分块查找

结合了顺序查找和折半查找，做到了块间有序，块内无序。块间可以使用折半查找，块内可以使用顺序查找。

平均查找长度

查找表总长度为 ，均匀地分为 块，每块大小为

如果索引部分使用顺序查找，则 ，当 时平均查找次数最小（均值不等式）

如果索引部分使用折半查找，则