6.4 折半查找法★2◎3

6.4 折半查找法★2◎3

　　有序表即数据元素按关键码升序或降序排列的表。
　　折半查找法也称为二分查找法，其基本思想为：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键码相等，则查找成功；若给定值小于中间元素的关键码，则在中间元素的左半区继续查找；若给定值大于中间元素的关键码，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域已无数据元素，则查找失败。
　　【折半查找步骤】

　　在有序表｛7，14，18，21，23，29，31，35，38，42，46，49，52｝中查找元素14的过程如下：

　　在上面的有序表中查找关键码为22的过程：

　　【算法分析】
　　从折半查找过程看，以表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表继续进行这种操作。所以，对表中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的二叉树为判定树。对于前面的有序表，按折半查找构造的判定树如图6-1所示。
　　可以看到，查找表中任一元素的过程，即是判定树中从根到该元素结点路径上各结点关键码的比较次数，也即该元素结点在树中的层次数。对于n个结点的判定树，树高为k，根据二叉树的性质有 n≤2k-1，即log2(n+1)≤k，所以k=〔log2(n+1)〕。因此，折半查找在查找成功时，所进行的关键码比较次数最多为〔log2(n+1)〕。

　　接下来讨论折半查找的平均查找长度。为便于讨论，以树高为k的满二叉树（n=2k-1）为例。假设表中每个元素的查找是等概率的，即则树的第i层有2i-1个结点，因此，折半查找的平均查找长度为：

　　所以，折半查找的时间效率为。虽然折半查找的平均查找效率高，但要求是有序表，链式存储的线性表无法适应折半查找算法。