不要记那个近似公式

参考链接开放定址法和拉链法的平均查找长度

写在前边的话：你的支持是我写作的动力，有帮助到你的话麻烦点赞加收藏呦。感激不尽！如有错误也请留言指正。

考研数据结构练习，欢迎订阅我的专辑《考研数据结构题型分类讲解练习》


【哈尔滨工业大学2005 四、1（8分）】画出对长度为18的有序的顺序表进行折半查找时的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。


判定树如下：




 查找成功时的



查找失败时




 

以4*13=52为例，解释一下数字的含义。

4：图中的□代表查找失败的节点，“4*13=52”这行的□需要查找四次。比如，对于16来说，查找到16需要四次，再往下找的时候判断它的左节点为空，而此时也就找到了□。
	
13：这行一共有13个□需要查找四次
	
52：这行查找失败的总次数是4*13次
写在后边的话：你的支持是我写作的动力，有帮助到你的话麻烦点赞加收藏呦。感激不尽！如有错误也请留言指正。

考研数据结构练习，欢迎订阅我的专辑《考研数据结构题型分类讲解练习》

建完全二叉树
例如长度为12的有序线性表，构建完全二叉树，如下图：



平均查找长度为：3.1

二分查找的平均查找长度
对二分查找的平均查找长度进行简单分析。
向作出假设：要查找的元素在数组内，数组长度为 $n$. 约定对长度为 $n$ 的数组，平均查找长度为随机变量 $C_n$，随机变量 $I_n$ 定义如下
$I_n=\left\{
\begin{matrix}
1 & 要查找的关键字是这个长度为 n 的数组的中间的关键字\\
0 & \mathrm{otherwise}
\end{matrix}
\right.,$
那么
$C_n=I_n+(1-I_n)(C_{n/2}+1),$
取其期望值
$E(C_n)=\frac1n+\left(1-\frac1n\right)E(C_{n/2}+1)<\frac1n+1+E(C_{n/2}),$
展开
$E(C_n)=\frac{1+\cdots+2^{\lfloor\log{n}\rfloor}}n+\lfloor\log{n}\rfloor+c=\Theta(\log {n}).$
简单分析，还有很多不完备的地方。