二分法查找电子教案.ppt

《二分法查找电子教案.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、7.3二分法查找理工学院：李红节选自《数据结构》第七章查找例：30个学生已按身高从低到高排好了队，新来的一名学生怎样找到自己的合适位置呢？顺序查找：特点是算法简单，但查找效率较低。二分法查找：又称折半查找，是一种查找效率较高的方法。问题：1、二分法查找的过程是什么？2、二分法查找算法如何实现？问题教学内容定义及要求基本思想查找过程算法实现重点与难点重点：1、查找过程2、算法实现难点：算法实现一、定义及要求1、二分法查找(BinarySearch)又称折半查找，它是一种查找效率较高的方法。2、要求：a、查找表中的记录按关键字有序排列b、只能在顺序存储结构上实现。二、基本思想每次将

2、给定值k与有序表中间位置上的记录关键字进行比较，确定待查记录所在的范围，然后逐步缩小查找范围，直到确定找到或找不到对应记录为止。三、查找过程1、注意：设有序表记录按关键字升序排列。2、设置整型变量：指示查找范围的下界：指示查找范围的上界：指示中间记录所在的位置，lowhighmidmid=(low+high)/23、查找过程：将给定值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：下界大于上界时01234567891011913153037556075809092lowhighmidr表例1：查找k=30的过程：成功：找到了k=30的位序为4（图1：查找k=30的示意图）01234567891011913153037556075809092lowhighmidr表例2：查找k=85的过程：失败：下界low>上界high，说明表

4、中没有关键字值等于85的记录。（图2：查找k=85的示意图）四、算法实现1、结点结构类型定义：（假设只有key域）structelement{intkey;};2、查找表存储结构定义：#defineMAXITEM100typedefstructelementsqlist[MAXITEM];3、二分法查找函数定义（成功：返回该关键字在表中的位序，否则返回-1）intbin_search(r,k,n)sqlistr;/*有序表r*/intk;/*待查关键字的值*/intn;/*有序表r中记录个数*/{intlow=1,high=n,mid;while(){mid=(low+high

5、)/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、适用条件：

6、a.有序表b.顺序存储结构2、基本思想：逐步缩小查找范围3、查找过程：定范围，找中间，比较，循环进行，直到结束4、算法实现：有效范围：low<=high若k>r[mid].keylow=mid+1若k