二分查找平均查找长度（假设满二叉树) ASLps=(n+1)/nlog(n+1)-1 ASLbs=-(20+21*2+.+21*h)Pi=员∑i*2-1(m=2h1) 令：S=hi*2-1=2i*2-2t+! 2∑b-1(t+1)2t-1 =20-1t*2t-1+2∑8-12t-1 =2(∑1t*2t-1-h*2h-1)+∑8-12 =2(S-h*2h-1)+2h-1 所以：S=h*2h-2h+1=(n+1)log2(n+1)-n ASLS=mtog2(0m+1）-1 ypb@ustc.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=