---
顺序查找
有序表的顺序查找
如果事先知道表中关键字有序，则查找失败时，不用一直比较到表的另一端才能知道失败信息，从而降低顺序查找失败时的ASL
对于n个关键字，查找失败共n+1种情况（对应n+1个区间），上式假设对于n个结点的查找概率相同，则相应的n+1个失败情况也等可能（p=1/(1+n)）
如果已知查找概率不等，另一种优化查找的方式是将被查概率大的关键字靠前放 ，从而提高查找成功的ASL（但这会破坏有序性，使得查找失败的ASL变大）
小结
无论如何优化，顺序查找的时间复杂度显然为O(n)
折半查找
（顺序表假设按升序排列）
基于查找判定树的效率分析
折半查找判定树的构造
precondition：计算mid时向下取整，因此右子树结点一定大于等于左子树节点，且最多多 1
构造时按照右优先添加结点
不拿看出，折半查找的判定树还是一棵二叉排序树：
折半查找的效率为O（log(n)）
小结
思考：如果mid使用向上取整呢？
分块查找
块内无序、块间有序
第 i 个块中的最大关键字要小于第 i+1 个块中所有记录的关键字
算法思想
如果在步骤①中使用折半查找，那么现在欲查找关键字19，折半查找会因为找不到19而失败吗？
注意体会上图说述的原因：
- 最终当 low>high 时，折半查找停止
- 此时low的左边一定小于目标关键字
- 而high的右边一定大于目标关键字
- 又因为分块存储的特性，每个索引项中保存的是各个分块的最大关键字
- 因此当折半查找停在 low>high 时，要到 low所指分块中去继续查找
查找效率分析
小结
