二分查找平均查找长度（假设满二叉树） ASLos=(n+1)/nlog(n+1)-1 ASLs-(2+21*2+.+2.1*h)Pi-是7i*21-1(=2h-1)） 令：S-1*2-1=-2211*2-2t+2骆-1(t+1)2t-1 =2∑0-1t*2t-1+2∑0-12t-1 =2(∑7t*2t-1-h*2h-1)+∑b-12 =2(S-h*2h-1)+2h-1 所以：S=h*2h-2h+1=(n+1)log2(n+1)-n ASLo-1s=+110g2(n+1)-1 ypb@ustc.edu.cn 5 中国科学技术大学 ypb@ustc.edu.cn 5 中国科学技术大学 二分查找平均查找长度（假设满二叉树） ASLbs＝（n＋1）/nlog(n+1)-1 ASLbs=(2 0+2 1*2+…+2 h-1*h)Pi=