分析二分查找成功时的平均查找长度

设计一个程序,建立由有序序列R[0..n-1]进行二分查找产生的判定树,在此基础上完成如下功能: (1) 输出n=11时的判定树并求成功情况下的平均查找长度ASl (2) 通过构造判定树可以求得的成功情况下的平均查找长度ASL1;当把含有n个节点的判定树看成是一棵满二叉树时,其成功情况下平均查找长度的人理论值ASL2约为log2(n+1)-1,对于内0,100,1000,10000,100000,1000000,求出其ASL1,ASL2和两者的差值。