二分法查找ppt课件.ppt
《二分法查找ppt课件.ppt》由会员分享,可在线阅读,更多相关《二分法查找ppt课件.ppt(16页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、7.3 二分法查找二分法查找理工学院:理工学院: 李李 红红 节选自节选自数据结构数据结构 第七章第七章 查找查找例例:30个学生已按身高从低到高排好了队,新来的一名学生怎样找到自己的合适位置呢?l顺序查找顺序查找:特点是算法简单,但查找效率较低。:特点是算法简单,但查找效率较低。l二分法查找二分法查找:又称折半查找,是一种查找效率较高的方:又称折半查找,是一种查找效率较高的方法。法。问题:问题:1、二分法查找的过程是什么?、二分法查找的过程是什么? 2、二分法查找算法如何实现、二分法查找算法如何实现?问问 题题教学内容教学内容l定义及要求l基本思想l查找过程l算法实现重点与难点重点与难点l重
2、点重点: 1、查找过程 2、算法实现l难点难点: 算法实现一、定义及要求一、定义及要求 1、二分法查找二分法查找(Binary Search) 又称折半查找,它是一种查找效率较高又称折半查找,它是一种查找效率较高的方法。的方法。 2、要求要求: a、查找表中的记录按关键字、查找表中的记录按关键字有序排列有序排列 b、只能在、只能在顺序存储结构顺序存储结构上实现。上实现。 二、基本思想二、基本思想 每次将给定值每次将给定值k与有序表与有序表中间位置中间位置上上的记录关键字进行的记录关键字进行比较比较,确定待查记录,确定待查记录所在的范围,然后逐步所在的范围,然后逐步缩小查找范围,缩小查找范围,直
3、到确定找到或找不到对应记录为止。直到确定找到或找不到对应记录为止。 三、查找过程三、查找过程1、注意、注意:设有序表记录按关键字升序排列。2、设置整型变量、设置整型变量 :指示查找范围的下界 :指示查找范围的上界 :指示中间记录所在的位置, lowhighmidmid = (low + high)/2 3、查找过程:、查找过程: 将给定值K和mid所指的记录关键字rmid.key比较 三种可能的结果: 查找成功并结束算法,mid所指的位置就是查到的记录所在的位置。 修改范围的上界: high = mid -1, 继续对左半部分进行二分查找。修改范围的下界: low = mid + 1, 继续对
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二分法 查找 ppt 课件
限制150内