算法：考察二分算法的平均成功查找长度1.5logn是如何计算出来的，请看图

Question

我想知道谁看懂了那个递推分析的过程，尤其是那个递推式。。。能给我讲解一下吗

Answer 1

你说的是C(k)那个递归式吗？如果是的话请看下面的一张图片

我们将(a)那一层想象成第k层，下面的(b)看作是k-1层。我们把第k层删掉，那么第k-1层就变成了顶层。
k-1层有两个分支，一左一右。你应该不难看出，顶层的查找长度（也就是一次查找成功的查找长度）必然是2。
那么对于左面的k-1层来说它的顶层是3，右面的顶层是4。稍加观察你会发现左面的k-1层的所有元素的查找长度都会相对于以k-1层为顶层时的查找长度多1。同样右面的k-1层的所有元素查找长度会相对于以k-1层为顶层时的查找长度多2。所以C(k)中需要把这些长度补上，然后在加上第k层的查找长度2即为C(k).