数据结构与算法——第9章-查找表-折半查找法(9.3)
一 概述
1 | 1.折半查找说明(有序) |
二 折半查找说明(有序)
1 | 折半查找,也称二分查找,在某些情况下相比于顺序查找,使用折半查找算法的效率更高。 |
三 折半查找算法
3.1 查找过程
一、步骤1
1 | 对静态查找表{5,13,19,21,37,56,64,75,80,88,92}采用折半查找算法查找关键字为 21 的过程为: |
二、步骤2
1 | 因此,再次遍历时需要更新 high 指针和 mid 指针的位置,令 high 指针移动到 mid 指针的左侧一个位置上, |
三、步骤3
1 | 同样,用 21 同 mid 指针指向的 19 作比较,19 < 21,所以可以判定 21 如果存在, |
1 | 当第三次做判断时,发现 mid 就是关键字 21 ,查找结束。 |
3.2 折半查找的实现代码:
1 | #include <stdio.h> |
以图 1 的查找表为例,运行结果为:
1 | 输入表中的数据元素: |
四 折半查找的性能分析
4.1 判定树
1 | 折半查找的运行过程可以用二叉树来描述,这棵树通常称为“判定树”。 |
4.2 说明
1 | 在判定树中可以看到,如果想在查找表中查找 21 的位置,只需要进行 3 次比较, |
五 总结
1 | 通过比较折半查找的平均查找长度,同前面介绍的顺序查找相对比,明显折半查找的效率要高。 |
六 参考
- C语言中文网—二分查找(折半查找)算法详解