博客

前面章节所介绍的有关在静态查找表中对特定关键字进行顺序查找、折半查找或者分块查找，都是在查找表中各关键字被查找概率相同的前提下进行的。

例如查找表中有 n 个关键字，表中每个关键字被查找的概率都是 1/n。在等概率的情况，使用折半查找算法的性能最优。

而在某些情况下，查找表中各关键字被查找的概率是不同的。例如水果商店中有很多种水果，对于不同的顾客来说，由于口味不同，各种水果可能被选择的概率是不同的。假设该顾客喜吃酸，那么相对于苹果和橘子，选择橘子的概率肯定要更高一些。在查找表中各关键字查找概率不相同的情况下，对于使用折半查找算法，按照之前的方式进行，其查找的效率并不一定是最优的。例如，某查找表中有 5 个关键字，各关键字被查找到的概率分别为：0.1，0.2，0.1，0.4，0.2(全部关键字被查找概率和为 1 )，则根据之前介绍的折半查找算法，建立相应的判定树为(树中各关键字用概率表示)：

图 1 折半查找对应的判定树

折半查找查找成功时的平均查找长度的计算方式为：

ASL = 判定树中各结点的查找概率*所在层次

所以该平均查找长度为：