6.4 折半查找法★2◎3

6.4 折半查找法★2◎3


6.4 折半查找法★2◎3
  有序表即数据元素按关键码升序或降序排列的表。

  折半查找法也称为二分查找法,其基本思想为…

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个结点,因此,折半查找的平均查找长度为:

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

6.4 折半查找法★2◎3

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部