有序表为（13,18,24,35,47,50,62,83,90,115,134）,二分查找法搜索成功和失败平均查找长度多少

Question

有序表为（13,18,24,35,47,50,62,83,90,115,134）,二分查找法搜索成功和失败平均查找长度多少

Answer 1

设内部结点的总数为n=2h-1,则判定树是深度为h=lg(n+1)的满二叉树(深度h不计外部结点).树中第k层上的结点个数为2k-1,查找它们所需的比较次数是k.因此在等概率假设下,二分查找成功时的平均查找长度为：
ASLbn≈lg(n+1)-1
　　二分查找在查找失败时所需比较的关键字个数不超过判定树的深度,在最坏情况下查找成功的比较次数也不超过判定树的深度.即为：
「lg(n+1) （取不小于lg(n+1)的整数的意思,右半边符号打不出）
根据公式,查找失败长度为4,平均查找长度约为2点多.