二分搜索法法下等概率条件下搜索失败和成功时的asl(平均搜索长度)是多少？

设内部节点总数为n=2h-1，则决策树是深度h=lg(n+1)的全二叉树(深度h不包括外部节点)。树的第k层节点数为2k-1，寻找它们所需的比较次数为k，因此，在等概率假设下，二分搜索法成功时的平均搜索长度为:

ASLbn≈lg(n+1)-1

当二分搜索法失败时，要比较的关键词数量不能超过决策树的深度，最差情况下，比较成功的数量不能超过决策树的深度。即:

二分搜索法的最差表现与平均表现相当接近。