二分法检索性能分析(续) ■成功的平均检索长度为: ASL≈1 (∑i·22) Nn+10g2(n+1)-1 ≈log2(n+1) (n>50) ■优缺点 优点:平均检索长度与最大检索长度相近,检索速度快 缺点:要排序、顺序存储,不易更新(插/删) 北京大学信息学院 版权所有,转载或翻印必究 Page 21北京大学信息学院 ©版权所有，转载或翻印必究 Page 21 二分法检索性能分析（续） ◼ 成功的平均检索长度为： (n > 50) ◼ 优缺点 ◼ 优点：平均检索长度与最大检索长度相近，检索速度快 ◼ 缺点：要排序、顺序存储，不易更新(插/删) 1 1 ASL ( 2 ) 1 1 log ( 1) 1 2 log ( 1) 1 2 j i i n i n n n n − =   = + = + −  + −