二分法查找ppt课件

7.3 二分法查找二分法查找理工学院：理工学院：李李 红红 节选自数据结构节选自数据结构 第七章第七章 查找查找7.3 二分法查找理工学院：李 红 节选自数据结构1例例：30个学生已按身高从低到高排好了队，新来的一名学生怎样找到自己的合适位置呢？l顺序查找顺序查找：特点是算法简单，但查找效率较低。：特点是算法简单，但查找效率较低。l二分法查找二分法查找：又称折半查找，是一种查找效率较高的方：又称折半查找，是一种查找效率较高的方法。法。问题：问题：1、二分法查找的过程是什么？、二分法查找的过程是什么？2、二分法查找算法如何实现、二分法查找算法如何实现？问问 题题例：30个学生已按身高从低到高排好了队，新来的一名学生怎样找2教学内容教学内容l定义及要求l基本思想l查找过程l算法实现教学内容定义及要求3重点与难点重点与难点l重点重点：1、查找过程 2、算法实现l难点难点：算法实现重点与难点重点：1、查找过程 4一、定义及要求一、定义及要求 1、二分法查找二分法查找(Binary Search)又称折半查找，它是一种查找效率较高又称折半查找，它是一种查找效率较高的方法。的方法。2、要求要求：a、查找表中的记录按关键字、查找表中的记录按关键字有序排列有序排列 b、只能在、只能在顺序存储结构顺序存储结构上实现。上实现。一、定义及要求5二、基本思想二、基本思想 每次将给定值每次将给定值k与有序表与有序表中间位置中间位置上上的记录关键字进行的记录关键字进行比较比较，确定待查记录所，确定待查记录所在的范围，然后逐步在的范围，然后逐步缩小查找范围，缩小查找范围，直到直到确定找到或找不到对应记录为止。确定找到或找不到对应记录为止。二、基本思想 每次将给定值k与有序表中间6三、查找过程三、查找过程1、注意、注意：设有序表记录按关键字升序排列。2、设置整型变量、设置整型变量 ：指示查找范围的下界 ：指示查找范围的上界 ：指示中间记录所在的位置，lowhighmidmid=(low+high)/2三、查找过程lowhighmidmid=(low+h7 3、查找过程：、查找过程：将给定值K和mid所指的记录关键字rmid.key比较 三种可能的结果：查找成功并结束算法,mid所指的位置就是查到的记录所在的位置。修改范围的上界:high=mid-1，继续对左半部分进行二分查找。修改范围的下界:low=mid+1，继续对右半部分进行二分查找。重复上述比较过程，区间每次缩小1/2，当区间不断缩小，出现查找区间的 ，宣告查找不成功并结束算法，确定关键字为K的记录不存在。（1）K=rmid.key：（2）K rmid.key：下界大于上界时下界大于上界时 3、查找过程：查找成功并结束算法,修改范围的801234567891011913153037556075809092lowhighmidr表表例1：查找k=30的过程：成功成功：找到了k=30的位序为 4（图1：查找k=30的示意图）012345678910119131530375560758901234567891011913153037556075809092lowhighmidr表表例2：查找k=85的过程：失败失败：下界low 上界high，说明表中没有关键字值等于85的记录。（图2：查找k=85的示意图）01234567891011913153037556075810四、算法实现四、算法实现1、结点结构类型定义：、结点结构类型定义：（假设只有（假设只有key域）域）struct element int key;2、查找表存储结构定义：、查找表存储结构定义：#define MAXITEM 100 typedef struct element sqlistMAXITEM;四、算法实现1、结点结构类型定义：（假设只有key域）113、二分法查找函数定义、二分法查找函数定义（成功：返回该关键字在表中的位序，否则返回（成功：返回该关键字在表中的位序，否则返回-1）int bin_search(r,k,n)sqlist r;/*有序表有序表r */int k;/*待查关键字的值待查关键字的值 */int n;/*有序表有序表r中记录个数中记录个数 */int low=1,high=n,mid;while()mid=(low+high)/2;/*求中点求中点*/if (k=rmid.key)return(mid);/*找到找到*/else if(krmid.key)else return(-1);/*失败失败*/low=mid+1;high=mid-1;low=high/*有效的查找范围有效的查找范围*/*在右半部分查找在右半部分查找/*/*在左半部分查找在左半部分查找*/3、二分法查找函数定义low=mid+1;high=mid-12五五.程序实现程序实现l运行程序:验证二分法查找函数的功能.五.程序实现运行程序:13课课 后后 作作 业业1、编写一程序、编写一程序：完成班级学生的信息顺序存储，在该信息表上用二分法查找学号为20和15的学生信息，成功输出该记录的值，不成功显示“该生不存在”的信息。2、预习：、预习：二叉判定树及二分法查找算法性能分析课 后 作 业1、编写一程序：14敬请指教！15小小 结结1、适用条件：适用条件：a.有序表 b.顺序存储结构2、基本思想基本思想：逐步缩小查找范围3、查找过程：查找过程：定范围，找中间，比较，循环进行，直到结束4、算法实现：算法实现：有效范围：lowrmid.key low=mid+1 若krmid.key high=mid-1重点重点重点难点重点难点小 结重点重点难点16