查找
本章在选择题中考察，重点理解折半查找的思想以及散列表查找的冲突处理方法。
## 查找
### 基本概念
### 顺序查找法
### 分块查找法
### 折半查找法
### 树形查找
- 二叉搜索树
- 平衡二叉树
- 红黑树
### B 树和 B+ 树的基本概念
### 散列表
### 字符串匹配模式
### 查找算法的分析和应用
查找前提与性能尺度
查找的目标是确定关键字是否存在并给出其位置；比较不同方法时，不能只记住复杂度，还要先检查数据是否满足前提：
- 顺序查找不要求有序，适合小规模或链接结构；
- 折半查找要求顺序存储且关键字有序，不能直接套到无序链表；
- 分块查找要求块间有序，并在索引表定位后于块内继续查找；
- 树形查找的效率取决于树高，二叉搜索树退化时会接近线性查找；
- 散列表以装填因子和冲突处理方式影响平均查找长度，不能把“哈希”误认为绝对常数时间。
题目问平均查找长度（ASL）时，应按每个关键字或查找失败位置出现的概率加权；题目未说明概率时，通常按等概率模型处理。成功与失败的查找路径不同，二者的 ASL 不能混用。