信息学奥赛辅导czh

《信息学奥赛辅导czh》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息学奥赛辅导湖中吴§9.1查找查找也称检索，就是在一组给定的数据中查找满足某种条件的数据，查找通常需要根据某一关键字进行。例如，在c盘中查找文件名为“cgf.txt”的文件。根据算法思想的不同，查找主要分为顺序查找和二分查找。1.顺序查找顺序查找是最基本的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，一一将扫描到的结点关键字和给定值K比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。A[i]x2325351382001108917

2、20【例9-1】输入一个整数X，在已存在的一个整数数组中顺序查找X是否存在，若找到，输出X在整数数组中所对应的位置，否则输出找不到的信息。（假设数组中没有重复数据）算法分析：（1）先输入待查的值K（2）令i=1，让k与a[i]比较（3）若a[i]<>k,则i:=i+1，如果i<=n然后转（3）继续进行比较，如果i.>n，则退出循环，输出找不到的信息；若a[i]=k，则退出循环，输出找到的信息。参考程序:Programex9_1;Constn=10varx,k,i:integer;a:array[1.

3、.n]ofinteger;found:Boolean;beginfori:=1tondoread(a[i]);readln;readln(x)i:=1;found:=false;while(i<=n)andnot(found)doifa[i]=xthenfound:=trueelsei:=i+1;iffoundthenwriteln(‘kat’,i:6)elsewriteln(‘notfound’);end.参考程序:Programex9_1;Constn=8varx,k,i:integer;a:a

4、rray[1..n]ofinteger;beginfori:=1tondoread(a[i]);readln;readln(x)i:=1;ForI:=1tondoifa[i]=xthenbeginwriteln(‘kat’,i:6);exit;endelseifI=nthenwriteln(‘notfound’);end.2.二分查找顺序查找要逐个比较表中元素，当表中元素非常多时,顺序查找的效率是很低的。二分查找是一种效率较高的查找方法，基于分治算法的思想，但二分查找要求线性表必须是有序的.我们不防

5、设有序表是递增有序的。二分查找的基本思想是：（设R[low..high]是当前的查找区间）(1)首先确定该区间的中点位置:mid=[(low+high)/2](2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下:1若R[mid].key>k,则由表的有序性可知R[mid..n].keys均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R[1..mid-1k]中,故新的查找区间是左边的子表R

6、[1..mid-1]。2类似地，若R[mid].key

7、12513025354256687279848890981031121201251302535425668727984889098103112120125130X=95fffhhhmidmidmid【例9-2】输入一整数X，在已存的一个有序整数数组中二分查找X是否存在，若找到，输出X在整数数组中所对应的位置，否则输出找不到的信息。（已知数组中没有重复数据）参考程序：Programex9_2Constn=16varm,f,h,x,i:integer;a:array[1..n]ofinteger;beg

8、inf:=1;h:=n;Fori:=1tondoread(a[i]);readln;Readln(x);Found:=false;While(f<=h)andnot(found)doBeginM:=trunc((f+h)/2);Ifx=a[m]thenfound:=trueElseifx