二分法查找

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