2023学年完整公开课版查找算法

第三单元查找算法考点与典例考点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】(2017·浙江省4月选考)小王编写了一个实现文字查找替换功能的VB程序,运行界面如图4-3-1所示。文本框Text1显示原文内容,Text2中输入查找内容,Text3中输入替换内容,单击“全部替换”按钮Command1后,Text4显示查找替换的结果,Text5中显示替换的次数,Text6显示“查找内容”在原文中的起始位置。实现上述功能的VB程序如下,但加框处代码有错,请改正。PrivateSubCommand1_Click()

DimsAsString,resuleAsString,posAsString

DimcountAsInteger,iAsInteger

i=1:count=0

resule="":pos=""

DoWhilei<=Len(Text1.Text)

s=Mid(Text1.Text,i,Len(Text2.Text))

Ifs=Text2.TextThen

result=result+Text3.Text

count=count+1

pos=pos+Str(count)′(1)

i=i+Len(Text2.Text)

Else

result=result+Text2.Text′(2)

i=i+1

EndIf

Loop

Text4.Text=result

Text5.Text=Str(count)

Text6.Text=posEndSub解析:本题利用顺序查找算法实现查找替换的功能。语句“Ifs=Text2.TextThen”表示在原文中找到了所要的查找内容时的情况,此时需要做的是:①将查找内容用替换内容代替(result=result+Text3.Text);②替换次数计数(count=count+1);③记录起始位置i(pos=pos+Str(i),添加在字符串pos中);④查找位置从当前位置前进Len(Text1.Text)个位置(i=i+Len(Text1.Text))。否则,将当前位置上的字符添加到字符串result中,因此(2)处语句修改为result=result+mid(Text1.Text,i,1)。答案:(1)pos+Str(i)

(2)result=result+mid(Text1.Text,i,1)【典例3】某8位男生的肺活量数据放在数组元素a(1)到a(8)中,其数据依次为“3104,3700,3058,3222,3621,3329,4233,4540”。使用顺序查找算法查找数据3339,则共需查找次数为(

)A.0 B.1 C.8 D.9解析:本题考查的是顺序查找算法的实现过程。由于给定的数列中没有数据3339,因此需要与数列中每个数进行比较,全部比较完后才知道查找失败,因此共需查找次数为8次。答案: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

EndIf

Loop

IfNotfindThenText2.Text="未找到!"

Text3.Text="共查找的次数为:"+Str(p)重难点剖析计算中点位置的语句还可以写成:m=Int((i+j)/2)或m=Fix((i+j)/2)。解析:本题主要考查的是对分查找算法。在[0,1]区间内查找一个数,第一次取[0,1]区间中间值0.5,每次都减少为原来的1/2,所以答案为D。答案:D

【典例4】已知单调函数在[0,1]区间存在一个x0,使f(x0)=0。现用对分查找算法搜索x0的值,开始搜索区间为[0,1],若经过10次对分查找后还需继续搜索,则第11次搜索区间的长度为(

)A.1/2 B.1/10 C.1/102 D.1/210【典例5】(2017·浙江11月选考)某算法的VB程序段如下:i=1:j=7:s=""key=Int(Rnd*100)DoWhilei<=j

m=(i+j)\2

Ifkey=a(m)Then

s=s+"M":ExitDo

′ExitDo表示退出循环

ElseIfkey<a(m)Then

j=m-1:s=s+"L"

Else

i=m+1:s=s+"R"

EndIfLoopText1.Text=s数组元素a(1)到a(7)的值依次为“24,35,38,41,45,69,78”。若该程序段执行后,文本框Text1中显示的内容可能是(

)A.RL B.LMR C.RLR D.LRLMC解析:本题主要考查的是对分查找算法。查找的结果有成功和不成功两种,若查找成功,则最后输出"M",如果查找不成功,则不会出现"M",因此"M"不可能出现在中间,故B选项错误。对n个数据查找,最多查找次数为log2n+1(向下取整),7个元素最多查找3次,因此可排除D选项。如果查找失败,则需要查找3次,即不可能查找2次就结束,因此A选项也错误。故答案为C。【典例6】(2017·浙江省4月选考)某对分查找算法的VB程序段如下:Key=Val(Text1.Text)i=1:j=10Text2.Text=""DoWhilei<=j

m=Int((i+j)/2+0.5)

IfKey=a(m)ThenExitDo

′ExitDo表示退出循环

IfKey<a(m)Thenj=m-1Elsei=m+1

Text2.Text=Text2.Text+Str(a(m))Loop数组元素a(1)到a(10)的值依次为“8,17,24,30,36,40,55,58,61,66”,文本框Text1中输入的值是30,执行该程序段,文本框Text2中显示的是(

)A.40

24 B.40

24

36 C.36

24 D.36

17

24解析:本题主要考查对分查找代码执行过程。具体查找过程如表所示:Key=30由此可知,共查找了4次,最后一次满足Key=a(m),执行ExitDo退出循环,其他几次的a(m)按次序依次显示在Text2中。答案:B

查找次数ijm=Int((i+j)/2+0.5)a(m)比较结果1110640Key<a(m)215324Key>a(m)345536Key<a(m)444430Key=a(m)【典例7】小明编写了一个查询学生的选考组合的VB程序。程序运行时,在列表框List1中显示所有学生的选考组合信息,在文本框Text1中输入学号,单击“开始查询”按钮(Command1),就开始查找该学号,如果找到,则在标签Label4中显示此学号对应的学生姓名和选考组合;如果没有找到,则显示信息“找不到此学号!”。程序的运行效果如图4-3-2所示。说明:(1)共有n名学生,其学号、姓名和选考组合信息分别存储在数组a,b,c中。(2)数据已按学生学号从小到大排列,第i个学生的学号保存在a(i),对应的姓名保存在b(i),选考组合保存在c(i)。实现上述功能的VB程序如下,在程序划线处填入适当的代码,把程序补充完整。DimnAsInteger′考生数Dima(1000)AsString,b(1000)AsString,c(1000)AsStringPrivateSubForm_Load()

′此过程用于输入n个学生的学号、姓名和选考组合,并分别存储在数组a、b、c中

′对学生信息按学号升序排序′将学生信息显示在列表框List1中′代码略EndSubPrivateSubCommand1_Click()

DimxAsString:DimposAsInteger

x=Text1.Text①

Ifpos>0ThenLabel4.Caption=b(pos)+"∶"+c(pos)

ElseLabel4.Caption="找不到此学号!"

EndIfEndSubFunctionSearch(KeyAsString)AsIntegerDimiAsInteger,jAsInteger,mAsInteger

i=1:j=n

DoWhilei<=j

m=Fix((i+j)/2)

IfKey=a(m)Then②

ExitFunction

′退出search函数ElseIf③

Then

j=m-1

Else

i=m+1

EndIf

Loop

Search=0EndFunction解析:本题主要考查的是对分查找算法。程序划线①处代码为调用函数,如果能找到该学号,则返回该学号在数组a中位置,根据“Ifpos>0Then”可知,将函数的返回值保存在变量pos中,因此划线①处的代码为pos=Search(x);函数的函数值是通过函数名来返回的,划线②处表示找到的情况,因此将返回该学号在数组a中的位置m,即划线②处代码为Search=m;数据已按学号升序排序,根据代码“j=m-1”可知,划线③处代码表示学号小于a(m)的情况,因此③处代码为a(m)>Key。答案:①pos=Search(x)②Search=m③a(m)>Key【典例8】编写VB程序,实现如下功能:在文本框Text1中输入一个整数,单击“查找删除”按钮Command1,采用对分查找法在数组A(从小到大排列,并显示在标签Label1中)中查找该数。若找到,则从数组A中删除该数(该数后面的数组元素都前移一位),并在标签Label2中显示删除后的结果,否则,在标签Label2中显示“该数没有找到”。程序运行效果如图4-3-3所示。实现上述功能的VB代码如下,但加框处代码有错,请改正。DimA(1To10)AsInteger′用于保存10个按从小到大顺序排列的整数Form_Load事件过程产生10个整数,按升序保存在数组A中,