第三单元 查找算法

第三单元查找算法夯实考点考点1顺序查找1.查找算法所谓查找就是在指定的数据中寻找某一特定的数据。查找结果有两种,找到(查找成功)和未找到(查找失败)。2.顺序查找的基本思想从第一个数据开始,从左往右(或从上到下)将数据按顺序逐个与给定的关键字进行比较,若某个数据和给定的关键字相等,则查找成功,找到并输出第一个与关键字相等的数据的位置;反之,查找失败。若有n个数,则可能的最多查找次数为n。3.顺序查找算法基本框架假设:要查找的数为key,待查找的数存放在数组d中。For语句框架:

Fori=1ton若d(i)=key,则表示找到,做相应处理

Nexti若i>n表示未找到DoWhile语句框架:

i=1

Dowhilei<=n若d(i)=key,则表示找到,做相应处理

i=i+1

Loop若i>n表示未找到4.顺序查找的程序实现在n个数组元素中依次查找,找到第1个满足条件的值,查找即结束,输出找到元素所在的位置;若找不到,输出“未找到”。程序实现:设:(1)要查找的数据是key(在文本框Text1中输入),查找的数据存放在数组d中。(2)pos为找到数的位置,pos=0表示未找到。(3)p记录查找的次数。key=Val(Text1.Text)

'Val要根据实际情况决定是否要添加

p=0

pos=0

find=False

'find=False表示未找到,find=True表示找到

i=1

DoWhilei<=nAndfind=False

'表示还没找完并且还未找到,则继续查找,notfind也可表示为find=False

p=p+1

Ifkey=d(i)Then

pos=i

find=True

EndIf

i=i+1

Loop

IffindThen'也可表示为Iffind=TrueThen

Text2.Text="在d("+Str(pos)+")中"

Else

Text2.Text="未找到"

EndIf典例1

某查找算法的部分VB代码如下:t=Falsei=0DoWhilei<7Andt=False

i=i+1

Ifa(i)=keyThent=TrueLoopIft=FalseTheni=0数组元素a(1)到a(7)的数据依次为“3,5,1,5,8,9,5”,当变量key值为5时,运用该算法处理后,变量i的值是(

)A.0 B.2 C.4 D.7解析:本题主要考查的是顺序查找的实现过程。本程序的功能是查找数组中第一个与目标数据相等的数,若找到将其在数组中的位置赋给变量i,结束查找;若找不到,变量i=0。因为目标值key=5,它和数组中第二个数正好相等,因此i=2。答案:B典例2编写一个VB程序,实现如下功能:在列表框List1中显示十个字符串,十个字符串存放在数组s中,在文本框Text1中输入一个字符串,单击“统计”按钮,统计字符串出现的次数,若出现次数大于0,则在文本框Text2中显示实际次数,若出现次数为0,则在文本框Text2中显示“找不到”。程序运行效果如图3-1所示。为实现上述功能,请在程序划线处填入合适的语句:程序①处语句为

;

程序②处语句为

;

程序③处语句为

。

解析:要查找的字符为st,st通过文本框Text1中输入得到,因此①处语句为Text1.Text;将要查找的字符串按顺序与数组s中元素比较,如果相等,则进行计数,因此②处语句为s(i)=st;根据题目“若出现次数大于0,则在文本框Text2中显示实际次数,若出现次数为0,则在文本框Text2中显示“找不到”。可知③处的语句为num>0或num<>0。答案:①Text1.Text②s(i)=st③num>0或num<>0典例3

某6位学生的学号存储在数组元素a(1)到a(6)中,其数据依次为“2015001,2015003,2015078,2015010,2015788,2015666”。使用顺序查找算法查找学号2015700,则共需查找次数为(

)A.0 B.5 C.6 D.7解析:本题考查的是顺序查找算法的实现过程。由于给定的数组中没有数据2015700,因此需要与数组中每个数进行比较,因此共需查找次数为6次。答案:C考点2对分查找1.对分查找的基本思想在有序的数据序列中(一般存放在数组中),首先把要查找的数据与数组中间位置的元素进行比较,如果相等,则查找成功并退出查找;否则,根据数组元素的有序性,确定数据应在数组的前半部分还是在后半部分查找;在确定了新的查找范围后,重复进行以上比较,直到找到或未找到为止。【重难点剖析】①对分查找的前提是被查找的数据序列必须是有序。②“未找到”是指当指定范围内的起点大于终点仍未找到该数据。2.对分查找算法基本框架说明:要查找的数为key,待查找的数存放在数组d中。

i为查找范围的起点,j为查找范围的终点,m为范围[i,j]的中间位置。

i=1

j=n

DoWhilei<=j计算中点位置m比较key与d(m),并做相应处理

Loop若i>j,则表示未找到3.对分查找程序实现在n个数组元素中依次查找,找到第1个满足条件的值,查找就结束,输出找到元素所在的位置;若找不到,输出“未找到”。程序实现:设要查找的数据是key(在文本框Text1中输入),查找的数据存放在数组d中。在文本框Text2中输出查找结果,若找到输出“找到!位置为:X”,否则输出“未找到!”在文本框Text3中输出共查找的次数。p表示查找的次数。核心代码为(以升序为例):key=Val(Text1.Text)

′表示要查找的数

p=0

′表示查找的次数

find=False

′查找的结果,若find=True表示找到,find=False表示未找到

i=1

′查找范围的起点

j=n

′查找范围的终点

DoWhilei<=jAndNotfind

′如果还未找完并且未找到

p=p+1

′查找次数计数

m=(i+j)/2

′计算中点位置m

Ifkey=d(m)Then

′表示找到的情况

find=True

Text2.Text="找到!位置为:"+Str(m)

EndIf

Ifkey>d(m)Then

′表示查找的数比中间位置上的数大时

i=m+1

Else

′表示查找的数比中间位置上的数小时

j=m-1

EndIfLoop

IfNotfindThenText2.Text="未找到!"Text3.Text="共查找的次数为:"+Str(p)【重难点剖析】计算中点位置的语句还可以写成:m=Int((i+j)/2)或m=Fix((i+j)/2)。典例4(2015浙江省10月选考题)已知单调函数在[0,1]区间存在一个x0,使f(x0)=0。现用对分查找算法搜索x0的值,开始搜索区间为[0,1],若经过10次对分查找后还需继续搜索,则第11次搜索区间的长度为(

)A.1/2 B.1/10 C.1/102 D.1/210解析:本题主要考查的是对分查找算法。在[0,1]区间内查找一个数,第一次取[0,1]区间中间值0.5,如果f(0.5)<0,则第二次区间为[0.5,1],如果f(0.5)>0,则第二次区间为[0,0.5],每次都减少为原来的1/2,所以答案为D。答案:D典例5a数组(a(1)～a(8))中存储了8本图书的价格,其数据依次为“105,98,95,60,55,35,12,8”。现使用对分查找数据8,需要查找的次数是(

)A.1 B.2 C.3 D.4解析:本题主要考查的是对分查找算法的实现过程。根据计算公式m=(i+j)/2可知,第一次访问的数据为60(第4个),第二次访问的数据为35(第6个),第三次访问的数据为12(第7个),第四次访问的数据为8(第8个),因此答案为D。答案:D典例6某数组有10个数据,依次为1,2,3,4,5,6,7,8,9,10,现要查找某一数据,若使用对分查找目标数据,需查找两次,若用顺序查找需查找8次,则要查找的目标数据为(

)A.2 B.3 C.7 D.8解析:本题考查的是两种查找算法。根据顺序查找次数即可判定目标数据为8,我们再用对分查找进行验证,第一次查找的位置是m=(1+10)/2=5,第二次查找的位置是m=(6+10)/2=8,第8个位置上的数就是8,因此答案为D。答案:D典例7小明编写了一个学生IC卡余额查询系统,其功能是在文本框Text1中输入学生的IC卡号,单击“查询余额”按钮Command1后,在标签Label3中输出查找结果。程序运行效果如图3-2所示。程序说明:(1)学生的IC卡号保存在数组card中,并已按升序排序好;卡中金额保存在数组money中。例:第i个学生的卡号保存在card(i)中,其对应的金额保存在money(i)中。(2)如果在数据库中找到此卡号,则在标签Label3中显示“此卡号余额为”及对应的余额,如果未找到则显示“查无此号!”。(3)程序运行,将在左边列表框List1中显示学生的卡号和金额。解决此问题的部分程序段如下:Constn=1500

′设共有n张卡Dimcard(1Ton)AsLongDimmoney(1Ton)AsSinglePrivateSubForm_Load()

′此过程用于输入卡号及金额,并存储在数组card和money中代码略EndSubPrivateSubCommand1_Click()DimxAsLong,iAsLong,jAsLong,mAsLong,findAsBooleanx=Val(Text1.Text)i=1

①

find=False

DoWhile②

m=(i+j)/2

Ifx=card(m)Then

③

ElseIfx<card(m)Then

j=m-1

Else

i=m+1

EndIfLoopIffind=TrueThen

Label3.Caption="此卡号余额为"+④+"元"

Else

Label3.Caption="查无此号!"

EndIfEndSub(1)解决此问题的算法是

。(选填:对分查找或顺序查找)

(2)在程序①,②,③,④划线处填入适当的语句或表达式,将程序补充完整:程序中①划线处应填入

。

程序中②划线处应填入

。

程序中③划线处应填入

。

程序中④划线处应填入

。

解析:本题考查的是对分查找算法的程序实现。对分查找的关键在于确定每次查找的范围,程序用变量i,j表示查找的范围,根据划线①处前面的语句可以确定①处的语句应表示首次查找范围的终点,即j=n;划线②处的语句表示查找的条件,如果还没找完并且还