顺序查找和折半查找错题要点
- 折半查找的判定树是平衡二叉树，左右子树高度差绝对值不超过 1。
- 折半查找的取整规则：要么统一向下取整，要么统一向上取整，且每次比较的元素只参与一次划分。
- 例：
[a, b, c, d, e, f]中查找a，向上取整先比较d，下一轮范围是[a ~ c]，d不再参与比较。
- 例：
- 二叉排序树的树高与输入序列的顺序有关，不同序列可能生成不同高度的树。
- 折半查找判定树中，左右子树的节点个数相差不超过 1（近似相等）。
- 分块查找的平均查找长度公式（假设每块大小相等）：
$$ ASL \approx \frac{s^2 + 2s + n}{2s} $$
其中：
- ( s )：每块元素个数
- ( n )：总元素个数
更常见的形式：
$$ ASL = \frac{s+1}{2} + \frac{n/s + 1}{2} $$
第一项是块内顺序查找的 ASL，第二项是块索引查找的 ASL。
- ASL 计算公式（一般形式）：
$$ ASL = \sum_{i=1}^{n} P_i \cdot C_i $$
其中 (P_i ) 是查找第 ( i ) 个元素的概率，( C_{i} ) 是比较次数。等概率时可简化为：
$$ ASL = \frac{1}{n} \sum_{i=1}^{n} C_i $$