静态查找表 折半查找的性能分析 (折半查找的过程可用二叉树来描述) 折半查找在查找成功时和给定值进行比较的关键字个数 至多为log2n+1 折半查找在查找不成功时和给定值进行比较的关键字个 数最多也不超过|og2n+1 成功平均查找长度: ASL=Σpc=1n2j.21=(n+1)n*og2(n+1)-1 (当n>50时) ASlbs=log2(n+1)-1静态查找表 ◼ 折半查找的性能分析 (折半查找的过程可用二叉树来描述) 折半查找在查找成功时和给定值进行比较的关键字个数 至多为 log2n +1 折半查找在查找不成功时和给定值进行比较的关键字个 数最多也不超过 log2n +1 成功平均查找长度： ASLbs= ∑pici=1/n∑j.2j-1=(n+1)/n*log2 (n+1)-1 （当n>50时） ASLbs=log2 (n+1)-1