二分法查找教学教材.ppt

《二分法查找教学教材.ppt》由会员分享，可在线阅读，更多相关《二分法查找教学教材.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、二分法查找二分法查找例例：30个学生已按身高从低到高排好了队，新来的一名学生怎样找到自己的合适位置呢？l顺序查找顺序查找：特点是算法简单，但查找效率较低。：特点是算法简单，但查找效率较低。l二分法查找二分法查找：又称折半查找，是一种查找效率较高的方：又称折半查找，是一种查找效率较高的方法。法。问题：问题：1、二分法查找的过程是什么？、二分法查找的过程是什么？2、二分法查找算法如何实现、二分法查找算法如何实现？问问 题题教学内容教学内容l定义及要求l基本思想l查找过程l算法实现重点与难点重点与难点l重点重点：1、查找过程 2、算法实现l难点难点：算法实现一、定义及要求一、定义及要求 1、二分法查

2、找二分法查找(Binary Search)又称折半查找，它是一种查找效率较高又称折半查找，它是一种查找效率较高的方法。的方法。2、要求要求：a、查找表中的记录按关键字、查找表中的记录按关键字有序排列有序排列 b、只能在、只能在顺序存储结构顺序存储结构上实现。上实现。二、基本思想二、基本思想 每次将给定值每次将给定值k与有序表与有序表中间位置中间位置上上的记录关键字进行的记录关键字进行比较比较，确定待查记录所，确定待查记录所在的范围，然后逐步在的范围，然后逐步缩小查找范围，缩小查找范围，直到直到确定找到或找不到对应记录为止。确定找到或找不到对应记录为止。三、查找过程三、查找过程1、注意、注意：设

3、有序表记录按关键字升序排列。2、设置整型变量、设置整型变量 ：指示查找范围的下界 ：指示查找范围的上界 ：指示中间记录所在的位置，lowhighmidmid=(low+high)/2 3、查找过程：、查找过程：将给定值K和mid所指的记录关键字rmid.key比较 三种可能的结果：查找成功并结束算法,mid所指的位置就是查到的记录所在的位置。修改范围的上界:high=mid-1，继续对左半部分进行二分查找。修改范围的下界:low=mid+1，继续对右半部分进行二分查找。重复上述比较过程，区间每次缩小1/2，当区间不断缩小，出现查找区间的 ，宣告查找不成功并结束算法，确定关键字为K的记录不存在。

4、（1）K=rmid.key：（2）K rmid.key：下界大于上界时下界大于上界时01234567891011913153037556075809092lowhighmidr表表例1：查找k=30的过程：成功成功：找到了k=30的位序为 4（图1：查找k=30的示意图）01234567891011913153037556075809092lowhighmidr表表例2：查找k=85的过程：失败失败：下界low 上界high，说明表中没有关键字值等于85的记录。（图2：查找k=85的示意图）四、算法实现四、算法实现1、结点结构类型定义：、结点结构类型定义：（假设只有（假设只有key域）域）st

5、ruct element int key;2、查找表存储结构定义：、查找表存储结构定义：#define MAXITEM 100 typedef struct element sqlistMAXITEM;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+h

6、igh)/2;/*求中点求中点*/if (k=rmid.key)return(mid);/*找到找到*/else if(krmid.key)else return(-1);/*失败失败*/low=mid+1;high=mid-1;low=high/*有效的查找范围有效的查找范围*/*在右半部分查找在右半部分查找/*/*在左半部分查找在左半部分查找*/五五.程序实现程序实现l运行程序:验证二分法查找函数的功能.课课 后后 作作 业业1、编写一程序、编写一程序：完成班级学生的信息顺序存储，在该信息表上用二分法查找学号为20和15的学生信息，成功输出该记录的值，不成功显示“该生不存在”的信息。2、预

7、习：、预习：二叉判定树及二分法查找算法性能分析小小 结结1、适用条件：适用条件：a.有序表 b.顺序存储结构2、基本思想基本思想：逐步缩小查找范围3、查找过程：查找过程：定范围，找中间，比较，循环进行，直到结束4、算法实现：算法实现：有效范围：lowrmid.key low=mid+1 若krmid.key high=mid-1重点重点重点难点重点难点进入夏天，少不了一个热字当头，电扇空调陆续登场，每逢此时，总会想起进入夏天，少不了一个热字当头，电扇空调陆续登场，每逢此时，总会想起那一把蒲扇。蒲扇，是记忆中的农村，夏季经常用的一件物品。记忆中的故那一把蒲扇。蒲扇，是记忆中的农村，夏季经常用的一

8、件物品。记忆中的故乡，每逢进入夏天，集市上最常见的便是蒲扇、凉席，不论男女老少，个个手持乡，每逢进入夏天，集市上最常见的便是蒲扇、凉席，不论男女老少，个个手持一把，忽闪忽闪个不停，嘴里叨叨着一把，忽闪忽闪个不停，嘴里叨叨着“怎么这么热怎么这么热”，于是三五成群，聚在大树，于是三五成群，聚在大树下，或站着，或随即坐在石头上，手持那把扇子，边唠嗑边乘凉。孩子们却在周下，或站着，或随即坐在石头上，手持那把扇子，边唠嗑边乘凉。孩子们却在周围跑跑跳跳，热得满头大汗，不时听到围跑跑跳跳，热得满头大汗，不时听到“强子，别跑了，快来我给你扇扇强子，别跑了，快来我给你扇扇”。孩。孩子们才不听这一套，跑个没完，直

9、到累气喘吁吁，这才一跑一踮地围过了，这时子们才不听这一套，跑个没完，直到累气喘吁吁，这才一跑一踮地围过了，这时母亲总是，好似生气的样子，边扇边训，母亲总是，好似生气的样子，边扇边训，“你看热的，跑什么？你看热的，跑什么？”此时这把蒲扇，此时这把蒲扇，是那么凉快，那么的温馨幸福，有母亲的味道！蒲扇是中国传统工艺品，在是那么凉快，那么的温馨幸福，有母亲的味道！蒲扇是中国传统工艺品，在我国已有三千年多年的历史。取材于棕榈树，制作简单，方便携带，且蒲扇的表我国已有三千年多年的历史。取材于棕榈树，制作简单，方便携带，且蒲扇的表面光滑，因而，古人常会在上面作画。古有棕扇、葵扇、蒲扇、蕉扇诸名，实即面光滑，因而，古人常会在上面作画。古有棕扇、葵扇、蒲扇、蕉扇诸名，实即今日的蒲扇，江浙称之为芭蕉扇。六七十年代，人们最常用的就是这种，似圆非今日的蒲扇，江浙称之为芭蕉扇。六七十年代，人们最常用的就是这种，似圆非圆，轻巧又便宜的蒲扇。蒲扇流传至今，我的记忆中，它跨越了半个世纪，圆，轻巧又便宜的蒲扇。蒲扇流传至今，我的记忆中，它跨越了半个世纪，也走过了我们的半个人生的轨迹，携带着特有的念想，一年年，一天天，流向长也走过了我们的半个人生的轨迹，携带着特有的念想，一年年，一天天，流向长长的时间隧道，袅长的时间隧道，袅结束