Question

假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数为　　　，则比较二次查找成功的结点数为　　　，

Answer 1

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+20）/ 2 = 10, 是10的位置，二分之后，1..9 变为 11..20

二次比较是(1+9) /2 =5, (11+20) /2 = 15，再次二分之后，变为1..4 6...9 11...14 16..20

其他类似上面分析，结果如最上面。