如何求折半查找的比较次数

问题描述:

如何求折半查找的比较次数
有一个长度为12的有序表,按对半查找法对该表进行查找,在表内元素等概率情况下,查找成功所需的平均幽会数次数是多少?
37/12.
我想问一下,是怎么求出来的?

先把它写成完全二叉树的形式:每次都从根结点开始,查找一次成功的有1个结点,二次有2个,三次有4个,四次有5个.
所以平均幽会数次数=(1*1+2*2+3*4+4*5)/12=37/12.