《信息学奥赛辅导》由会员分享，可在线阅读，更多相关《信息学奥赛辅导（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、二分查找,二分查找的基本思想: 、原来的数据序列是有序的。 、先检查要找的数与中间位置的元素值是否相等。若相等，则查找成功;若不等，如果查找数大于中间数则在数据序列的后半部分查找，反之在数据序列的前半部分查找。 、重复，直到找到或查无此数为止。,在解决实际问题时,我们最容易想到的降低运算规模的分治方法就是二分法.,
