《信息学奥赛辅导》由会员分享,可在线阅读,更多相关《信息学奥赛辅导(15页珍藏版)》请在金锄头文库上搜索。
1、,信息学奥赛辅导,9.1 查找查找也称检索,就是在一组给定的数据中查找满足某种条件的数据,查找通常需要根据某一关键字进行。例如,在c盘中查找文件名为“cgf.txt”的文件。根据算法思想的不同,查找主要分为顺序查找和二分查找。 1.顺序查找 顺序查找是最基本的查找方法,它的基本思想是:从表的一端开始,顺序扫描线性表,一一将扫描到的结点关键字和给定值K比较。若当前扫描到的结点关键字与K相等,则查找成功;若扫描结束后,仍未找到关键字等于K的结点,则查找失败。,Ai,x,23,25,3,5,138,200,110,89,17,20,【例9-1】 输入一个整数X,在已存在的一个整数数组中顺序查找X是否
2、存在,若找到,输出X在整数数组中所对应的位置,否则输出找不到的信息。(假设数组中没有重复数据),算法分析: (1) 先输入待查的值K (2) 令i=1,让k与ai比较 (3) 若aik,则i:=i+1,如果in,则退出循环,输出找不到的信息;若ai=k,则退出循环,输出找到的信息。,参考程序: Program ex9_1; Constn=10 varx,k,i:integer; a:array1n of integer;found:Boolean; beginfor i:=1 to n do read(ai);readln;readln(x)i:=1;found:=false;while (i
3、k,则由表的有序性可知Rmidn.keys均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R1mid-1k中,故新的查找区间是左边的子表R1mid-1。 2类似地,若Rmid.keyK,则要查找的K必在mid的右子表rmid+1n中,即新的查找区间R1n开始,每间经过一次与当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点,或者直至当前的查找区间为空(即查找失败)时为止。,Ai,f,h,mid,X=95,f,f,f,h,h,h,mid,mid,mid,【例9-2】输入一整数X,
4、在已存的一个有序整数数组中二分查找X是否存在,若找到,输出X在整数数组中所对应的位置,否则输出找不到的信息。(已知数组中没有重复数据),参考程序: Program ex9_2 Const n=16 varm,f,h,x,i:integer;a:array1n of integer; beginf:=1;h:=n;For i:=1 to n do read(ai); readln; Readln(x); Found: =false; While (f=h)and not (found) doBegin M:=trunc(f+h)/2); If x=am then found: =trueElse
5、 if xam then h:=m-1Else f:=m+1End; If found then writeln(x:6,at,m:6)Else writeln(not found!); End.,以点带面,二分查找 的递归出程序,const n=100; var a: array1n of integer;x, i :integer; procedure search(x,top,bot:integer);var mid:integer; beginif ( )then beginmid:=(top+bot) div 2;if x=amid then writeln(yes)else if
6、xamid then search( )else search( );endelse writeln(no);end;beginfor i:=1 to n do read(ai);readln(x);search(x,1,n);end.,top=bot,x,top,mid-1,x,mid+1,bot,二分查找 的递归出程序:,分治法,当我们处理大规模问题时,求解可能比较困难。对于这类问题,我们往往先把它分解成若干个与原问题类型相同的子问题求解,求出这几个子问题的解后,再找到合适的方法,把它们组合成整个问题的解。如果处理子问题仍然有困难,则再次进行分割,直到可以直接求解为止。这种大化小的策略称为
7、分治策略。二分查找、归并排序、快速排序都是应用分治策略的典型例子。,用分治思想设计出的算法在每一层递归上都有三个步骤:、分割,将要解决的问题划分成若干个规模较小的同类问题;、求解,递归地解各个子问题,当子问题划分得足够小时,则直接解之;、合并,将子问题的解合并成原问题的解。,由于分治策略是把问题分成较小的与原问题类型相同的子问题,对于问题的处理过程与原问题的处理过程是相同的,所以分治法处理问题过程,可以自然地写成一个递归的处理过程。,例1、二分查找,二分查找的基本思想: 、原来的数据序列是有序的。 、先检查要找的数与中间位置的元素值是否相等。若相等,则查找成功;若不等,如果查找数大于中间数则在数据序列的后半部分查找,反之在数据序列的前半部分查找。 、重复,直到找到或查无此数为止。,在解决实际问题时,我们最容易想到的降低运算规模的分治方法就是二分法.,