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