折半查找法
标签: 数据结构
学习人数: 21.7k

折半查找,也称二分查找,在某些情况下相比于顺序查找,使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。

例如,在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使用折半查找算法查找数据之前,需要首先对该表中的数据按照所查的关键字进行排序:{5,13,19,21,37,56,64,75,80,88,92}。

在折半查找之前对查找表按照所查的关键字进行排序的意思是:若查找表中存储的数据元素含有多个关键字时,使用哪种关键字做折半查找,就需要提前以该关键字对所有数据进行排序。

 

折半查找算法
对静态查找表{5,13,19,21,37,56,64,75,80,88,92}采用折半查找算法查找关键字为 21 的过程为:


 

如上图所示,指针 low 和 high 分别指向查找表的第一个关键字和最后一个关键字,指针 mid 指向处于 low 和 high 指针中间位置的关键字。在查找的过程中每次都同 mid 指向的关键字进行比较,由于整个表中的数据是有序的,因此在比较之后就可以知道要查找的关键字的大致位置。

例如在查找关键字 21 时,首先同 56 作比较,由于21 < 56,而且这个查找表是按照升序进行排序的,所以可以判定如果静态查找表中有 21 这个关键字,就一定存在于 low 和 mid 指向的区域中间。

因此,再次遍历时需要更新 high 指针和 mid 指针的位置,令 high 指针移动到 mid 指针的左侧一个位置上,同时令 mid 重新指向 low 指针和 high 指针的中间位置。如图所示:

同样,用 21 同 mid 指针指向的 19 作比较,19 < 21,所以可以判定 21 如果存在,肯定处于 mid 和 high 指向的区域中。所以令 low 指向 mid 右侧一个位置上,同时更新 mid 的位置。


当第三次做判断时,发现 mid 就是关键字 21 ,查找结束。

注意:在做查找的过程中,如果 low 指针和 high 指针的中间位置在计算时位于两个关键字中间,即求得 mid 的位置不是整数,需要统一做取整操作。

折半查找的实现代码:

//折半查找算法
int Binary_Search(SeqList L, ElemType key) {
    int low = 1;  //初始状态 low 指向第一个关键字
    int high = L.length;  //high 指向最后一个关键字
    int mid;
    while (low <= high) {
        mid = (low+high) / 2;  // int 本身为整形,所以,mid 每次为取整的整数
        if (L.elem[mid].key == key)// 如果 mid 指向的同要查找的相等,返回 mid 所指向的位置
            return mid;
        else if(L.elem[mid].key > key)// 如果mid指向的关键字较大,则更新 high 的位置
            high = mid-1;
        else // 反之,则更新 low 的位置
            low = mid + 1;
...
登录查看完整内容


课后作业

课后习题

 

【2017年真题】下列二叉树中,可能成为折半查找判定树(不含外部结点)的是()

参考答案:A

 

【2015年真题】下列选项中,不能构成折半查找中关键字比较序列的是()。

A.500,200,450,180    B.500,450,200,180
C.180,500,200,450    D.180,200,500,450

参考答案:A

 

【2010年真题】已知一个长度为 16 的顺序表 L,其元素按关键字有序排列。若采用折半查 找法查找一个 L 中不存在的元素,则关键字的比较次数最多的是()。 
A.4 B.5 C.6 D.7 

参考答案:B
答案解析:考查折半查找的过程。 
具有 n 个结点的判定树的高度为log2n + 1,长度为 16,高度为 5,所以最多比较 5 次。 


登录后开始许愿

暂无评论,来抢沙发