假设在有序线性表A[1..20]上进行二分查找,则比较一次查找成功的结点数为   ,则比较二次查找成功的结点数为   ,
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

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