Question

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

假设在有序线性表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
其他类似上面分析，结果如最上面。

追问

二分到底是怎么二分的？？？取一半？？假如是偶数的个数怎么取啊？还有这个节点数怎么看的？？？

追答

二分就是将数列分为两半。 比如，a b c d， 你要查找a的话，首先取中间数(一般的代码中，写法是(low + high) / 2 即（0+3）/2 = 1 ,数组从0开始)，就是位置1的数，这里是b，a比b小，继续查找b左边的数列，这时(low + high ) /2 为 （0+ 0）/2就是0的位置，为a，查找成功。

结点就是a b c d 这些，比如上面的b，一次比较就找到了，a 、c比较两次就找到，d要比较三次。