查找

简要讨论

本章内容极易忘，不贴合实际算法

需要读者通过刷题反复记忆，练到**（重要公式）**熟记于心即可

普通线性表查找

利用 高斯求和公式 算出成功时的查找期望

失败的查找次数是唯一的 $P(p=1)\cdot C(i)=n$

有序优化

一般线性表的 失败查找次数 远远大于 成功查找次数；

但是设计成有序表去查找，就能做到同规模下 几乎一样的查找次数

失败的查找次数为 $n+1$，因此平均失败查找次数：

$\sum _{i=1}^{n}P\left(p=\frac{1}{n+1}\right)\cdot C(i)=\frac{1+2+\cdot \cdot \cdot +n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$

折半查找

注意

计算 下一个根节点编号 时，取整一定要 一致 ， 要么向上取整，要么向下取整

折半查找判定树 本身是 平衡二叉排序树

但是其本质是一个静态的数组，而非可以动态维护的树结构

分块查找