Question

假设在有序线性表A[1..20]上进行二分查找 平均查找长度为?

为什么答案给的是3.7呢？不是应该是log2 (n+1)=log2 21么?
请问3.7是怎么算出来的，求详细过程!!

Answer 1

比较次数，为了直观一点，如下，第一排为各个数，接下来的5排为查找对应上面的数的查找比较次数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1
2 2
3 3 3 3
4 4 4 4 4 4 4 4
5 5 5 5 5
总共比较次数为：1 +2*2 + 4*3 + 8*4+ 5*5 = 74
平均长度是 74 /20 =3.7

可以这样算，二分查找就是将数列不停的二分
一个数列中间只有1个数，比较1次
二分后变为2个数列
然后查找这2个数列的中间数，比较次数等于 2个数列 * 2次
继续二分变为4个数列，比较次数变为 4 * 3
继续比较次数为8*4
继续比较次数为16*5，然而，这里的数只有20个，这里16显然多了，20 - 8 - 4 -2 -1 = 5，是5*5

以后你可以按照公式1+2*2 + ...2^(n-1) * n 来算总的比较次数。

log2(n+1)是理想的平均情况，近似值。