《二分法查找》由会员分享，可在线阅读，更多相关《二分法查找（16页珍藏版）》请在金锄头文库上搜索。
1、7 3二分法查找 理工学院 李红 节选自 数据结构 第七章查找 例 30个学生已按身高从低到高排好了队 新来的一名学生怎样找到自己的合适位置呢 顺序查找 特点是算法简单 但查找效率较低 二分法查找 又称折半查找 是一种查找效率较高的方法 问题 1 二分法查找的过程是什么 2 二分法查找算法如何实现 问题 教学内容 定义及要求基本思想查找过程算法实现 重点与难点 重点 1 查找过程2 算法实现难点 算法实现 一 定义及要求 1 二分法查找 BinarySearch 又称折半查找 它是一种查找效率较高的方法 2 要求 a 查找表中的记录按关键字有序排列b 只能在顺序存储结构上实现 二 基本思想 每
2、次将给定值k与有序表中间位置上的记录关键字进行比较 确定待查记录所在的范围 然后逐步缩小查找范围 直到确定找到或找不到对应记录为止 三 查找过程 1 注意 设有序表记录按关键字升序排列 2 设置整型变量 指示查找范围的下界 指示查找范围的上界 指示中间记录所在的位置 low high mid mid low high 2 3 查找过程 将给定值K和mid所指的记录关键字r mid key比较三种可能的结果 查找成功并结束算法 mid所指的位置就是查到的记录所在的位置 修改范围的上界 high mid 1 继续对左半部分进行二分查找 修改范围的下界 low mid 1 继续对右半部分进行二分查找
3、 重复上述比较过程 区间每次缩小1 2 当区间不断缩小 出现查找区间的 宣告查找不成功并结束算法 确定关键字为K的记录不存在 1 K r mid key 2 Kr mid key 下界大于上界时 r表 例1 查找k 30的过程 成功 找到了k 30的位序为4 图1 查找k 30的示意图 r表 例2 查找k 85的过程 失败 下界low 上界high 说明表中没有关键字值等于85的记录 图2 查找k 85的示意图 四 算法实现 1 结点结构类型定义 假设只有key域 structelement intkey 2 查找表存储结构定义 defineMAXITEM100typedefstructele
4、mentsqlist MAXITEM 3 二分法查找函数定义 成功 返回该关键字在表中的位序 否则返回 1 intbin search r k n sqlistr 有序表r intk 待查关键字的值 intn 有序表r中记录个数 intlow 1 high n mid while mid low high 2 求中点 if k r mid key return mid 找到 else if k r mid key else return 1 失败 low mid 1 high mid 1 low high 有效的查找范围 在右半部分查找 在左半部分查找 五 程序实现 运行程序 验证二分法查找函数的功能 课后作业 1 编写一程序 完成班级学生的信息顺序存储 在该信息表上用二分法查找学号为20和15的学生信息 成功输出该记录的值 不成功显示 该生不存在 的信息 2 预习 二叉判定树及二分法查找算法性能分析 敬请指教 小结 1 适用条件 a 有序表b 顺序存储结构2 基本思想 逐步缩小查找范围3 查找过程 定范围 找中间 比较 循环进行 直到结束4 算法实现 有效范围 lowr mid keylow mid 1若k r mid keyhigh mid 1 重点 重点难点
