二分査找平均查找长度(假设满二叉树) ASLhe=(n+1)/nlog(n+1) ASLb=(20+2*2+…+21+h)Pin21*2-(n=21 i=t+1 令:S=∑hi*21-1=*24-2 2zb-1(t+1)2-1 b-1t*2-1+2b-12-1=2b1(t+1)2-1 2(ht*2-1-h*2h-1)+2b12 =2(S-h*2h-)+2h-1 所以:S=h*2h-2h+1=(n+1)log2(n+1)-n aSls=S=log2(n+1)-1 pboustc. edu. cn 中国科学技术大学ypb@ustc.edu.cn 7 中国科学技术大学 二分查找平均查找长度（假设满二叉树） ASLbs＝（n＋1）/nlog(n+1)-1 ASLbs=(2 0+2 1*2+…+2 h-1*h)Pi=