一个对半查找的新算法

<正> 在计算机的信息检索方面,对半查找是极其重要的一种方法。一个文件的n个记录已经按记录的关键码排序,当,n=2~M-1(M为正整数)时,对半查找对应着一棵完全二叉分类树。当n≠2~M-1时,所对应的就不是一棵完全树。此时,对半查找的最佳分类树是一棵对称二叉分类树(本文所讨论的,都是查找概率为平均值的情况,即对统一记录有Pi=1/n),因其平均查找路径最短。 本文将讨论一个对半查找的新算法。计算法对任一个n都可以形成一棵对称二叉分类树。