请问在二分查找的方法下,在等概率情况下,查找失败和成功时的asl(平均查找长度)是多少啊?
请问:长度为12的按关键字排序的查找表采用顺序组织结构,则在二分查找的方法下,在等概率情况下,查找失败和成功时的asl(平均查找长度)分别是多少啊?
是不是37/12 和49/13?
主要想知道为什么..
参考答案:设内部结点的总数为n=2h-1，则判定树是深度为h=lg(n+1)的满二叉树(深度h不计外部结点)。树中第k层上的结点个数为2k-1，查找它们所需的比较次数是k。因此在等概率假设下，二分查找成功时的平均查找长度为：
ASLbn≈lg(n+1)-1
二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为：
二分查找的最坏性能和平均性能相当接近。