《对半查找算法》教学课件1.pptVIP

对半查找方法（数组的应用）对半查找复习：顺序查找，即从第一个元素开始，顺序查下去直到找到或查到最后一个元素为止。查找是按关键字（keyword）进行，可以唯一地把资料区分出来的数据被称为主关键字。如学生的资料：intid;//学号charname[20];//姓名charsex;//性别intage;//年龄charaddress[60];//家庭地址floateng,phy,electron;//英语,物理和电子学成绩学号可作为主关键字。如果关键字小的排在前面，我们称为升序排列，反之为降序排列。这时可以采用对半查找（binarysearch）。首先安排两个指针low和high指向首尾两元素，取mid=(low+high)/2，如mid指向元素是所查找的，则结束。如果该元素关键字大了，则取low=mid+1，high不变，继续查找；如果该元素关键字小了，则取high=mid-1，low不变，继续查找。如果查到lowhigh仍未找到，则失败，停止。1.对半查找low8917131120719212331262925373923查找lowmidhigh2021292623313739midhighlow202123midhigh23lowmidhigh成功图查找成功例25781113179192023212629313710查找low39midhigh25781113179lowmidhigh1113179lowmidhigh9lowmidhigh图查找失败例这里有一步非常重要:就是low=mid+1和high=mid-1，没有加１和减１时，可能数据存在而找不到。如在图中，如果找到了仅剩20、21、23这一步，这时取low=mid，则剩下21、23，mid=(low+high)/2,得mid=low,下一步low=mid,还是剩下21、23，mid永远不能指向23，永远找不到23了。对半查找递归算法，作为有序表模板类成员函数。递归方法易读易懂，但效率低。注意递归的隐式循环代码编写。对半查找迭代算法该例中迭代算法的可读性也不差，效率要高于递归。注意迭代的显式循环代码编写的关键点。3.对半查找【例】对半查找递归算法intBinarysearch(intslist[],intx,intlow,inthigh){//x为定值intmid=-1;if(low=high){mid=(low+high)/2;if(slist[mid]x)mid=Binarysearch(slist,x,mid+1,high); //中间点小于定值，查找右区间，注意mid+1elseif(xslist[mid])mid=Binarysearch(slist,x,low,mid-1); //中间点大于定值，查找左区间，注意mid-1}returnmid;//找到返回下标;未找到但结束了，返回mid不加判断}递归方法易读易懂，但效率低。注意递归的隐式循环代码编写。【例】对半查找递归算法voidmain(){constinth=19;inti,k=47;inta[h]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};print(a,h);i=Binarysearch(a,k,0,h-1);cout系数k在表中位置（下标）：iendl;}voidprint(intslist[],intlast){ inti; for(i=0;i=last;i++) coutslist[i]; coutendl;}【例】对半查找迭代算法intBinarySearch(intslist[],intx,intlast){inthigh=last,low=0,mid;//last当前有序表最大下标while(low=high){ mid=(low+high)/2; if(xslist[mid]) high=mid-