1、第三单元查找算法第三单元查找算法考点与典例考点与典例考点考点1 1 顺序查找顺序查找 1.1.查找算法查找算法所谓查找就是在指定的数据中寻找某一特定的数据。所谓查找就是在指定的数据中寻找某一特定的数据。查找结果有两种查找结果有两种: :找到找到( (查找成功查找成功) )和未找到和未找到( (查找失败查找失败) )。2.2.顺序查找的基本思想顺序查找的基本思想从第一个数据开始从第一个数据开始, ,从左往右从左往右( (或从上到下或从上到下) )将数据按顺序逐个与给定的关键字将数据按顺序逐个与给定的关键字进行比较进行比较, ,若某个数据和给定的关键字相等若某个数据和给定的关键字相等, ,则查找成
2、功则查找成功, ,找到并输出第一个与找到并输出第一个与关键字相等的数据的位置关键字相等的数据的位置; ;反之反之, ,查找失败。若有查找失败。若有n n个数个数, ,则可能的最多查找次则可能的最多查找次数为数为n n。3.3.顺序查找算法基本框架顺序查找算法基本框架假设假设: :要查找的数为要查找的数为key,key,待查找的数存放在数组待查找的数存放在数组d d中。中。ForFor语句框架语句框架: :For i=1 To nFor i=1 To n若若d(id(i)=key,)=key,则表示找到则表示找到, ,做相应处理做相应处理Next iNext i若若inin表示未找到表示未找到D
3、o WhileDo While语句框架语句框架: :i=1i=1Do While i=nDo While inin表示未找到表示未找到4.4.顺序查找的程序实现顺序查找的程序实现在在n n个数组元素中依次查找个数组元素中依次查找, ,找到第找到第1 1个满足条件的值个满足条件的值, ,查找即结束查找即结束, ,输出找输出找到元素所在的位置到元素所在的位置; ;若找不到若找不到, ,输出输出“未找到未找到”。程序实现程序实现: :设设:(1):(1)要查找的数据是要查找的数据是key(key(在文本框在文本框Text1Text1中输入中输入),),查找的数据存放在数查找的数据存放在数组组d d中
4、。中。(2)pos(2)pos为找到数的位置为找到数的位置,pos=0,pos=0表示未找到。表示未找到。(3)p(3)p记录查找的次数。记录查找的次数。key=Val(Text1.Text)key=Val(Text1.Text)ValVal要根据实际情况决定是否要添加要根据实际情况决定是否要添加p=0p=0pos=0pos=0find=Falsefind=Falsefind=Falsefind=False表示未找到表示未找到,find=True,find=True表示找到表示找到i=1i=1Do While i=n And find=FalseDo While i=n And find=Fa
5、lse表示还没找完并且还未找到表示还没找完并且还未找到, ,则继续查找则继续查找,not ,not findfind也可表示为也可表示为find=Falsefind=Falsep=p+1p=p+1If key=If key=d(id(i) Then) Thenpos=ipos=ifind=Truefind=TrueEndIfEndIfi=i+1i=i+1LoopLoopIf find Then If find Then 也可表示为也可表示为If find=True ThenIf find=True ThenText2.Text=Text2.Text=在在d(+Str(posd(+Str(pos
6、)+)+)中中 ElseElseText2.Text=Text2.Text=未找到未找到 EndIfEndIf【典例典例1 1】某查找算法的部分某查找算法的部分VBVB代码如下代码如下: :t=Falset=Falsei=0i=0Do While i7 And t = FalseDo While i7 And t = Falsei=i+1i=i+1If If a(ia(i)=key Then t=True)=key Then t=TrueLoopLoopIf t=False Then i=0If t=False Then i=0数组元素数组元素a(1)a(1)到到a(7)a(7)的数据依次为的
7、数据依次为“3,5,1,5,8,9,5”,3,5,1,5,8,9,5”,当变量当变量keykey值为值为5 5时时, ,运用该算法处理后运用该算法处理后, ,变量变量i i的值是的值是( () )A.0A.0B.2B.2C.4C.4D.7D.7解析解析: :本题主要考查的是顺序查找的实现过程。本程序的功能是查找数组中本题主要考查的是顺序查找的实现过程。本程序的功能是查找数组中第一个与目标数据相等的数第一个与目标数据相等的数, ,若找到将其在数组中的位置赋给变量若找到将其在数组中的位置赋给变量i,i,结束查结束查找找; ;若找不到若找不到, ,变量变量i=0i=0。因为目标值。因为目标值key=
8、5,key=5,它和数组中第二个数正好相等它和数组中第二个数正好相等, ,因因此此i=2i=2。 答案答案: :B B 【典例典例2 2】 ( (20172017浙江省浙江省4 4月选考月选考) )小王编写了一个实现文字查找替换功能小王编写了一个实现文字查找替换功能的的VBVB程序程序, ,运行界面如图运行界面如图4-3-14-3-1所示。文本框所示。文本框Text1Text1显示原文内容显示原文内容,Text2,Text2中输中输入查找内容入查找内容,Text3,Text3中输入替换内容中输入替换内容, ,单击单击“全部替换全部替换”按钮按钮Command1Command1后后,Text4,
9、Text4显示查找替换的结果显示查找替换的结果,Text5,Text5中显示替换的次数中显示替换的次数,Text6,Text6显示显示“查找内查找内容容”在原文中的起始位置。在原文中的起始位置。实现上述功能的实现上述功能的VBVB程序如下程序如下, ,但加框处代码有错但加框处代码有错, ,请改正。请改正。Private Sub Command1_Click()Private Sub Command1_Click()Dim s As String, Dim s As String, resuleresule As String, pos As String As String, pos As S
10、tringDim count As Integer, i As IntegerDim count As Integer, i As Integeri = 1:count = 0i = 1:count = 0resuleresule = : pos = = : pos = Do While i = Len(Text1.Text)Do While i = Len(Text1.Text)s = Mid(Text1.Text, i, Len(Text2.Text)s = Mid(Text1.Text, i, Len(Text2.Text)If s = Text2.Text ThenIf s = Tex
11、t2.Text Thenresult = result+Text3.Textresult = result+Text3.Textcount = count+1count = count+1pos = pos+Str(count)(1)pos = pos+Str(count)(1)i = i+Len(Text2.Text)i = i+Len(Text2.Text)ElseElseresult = result+Text2.Text(2)result = result+Text2.Text(2)i = i+1i = i+1End IfEnd IfLoopLoopText4.Text = resul
12、tText4.Text = resultText5.Text = Text5.Text = Str(countStr(count) )Text6.Text = posText6.Text = posEnd SubEnd Sub解析解析: :本题利用顺序查找算法实现查找替换的功能。语句本题利用顺序查找算法实现查找替换的功能。语句“If s = If s = Text2.Text Then”Text2.Text Then”表示在原文中找到了所要的查找内容时的情况表示在原文中找到了所要的查找内容时的情况, ,此时需此时需要 做 的 是要 做 的 是 : : 将 查 找 内 容 用 替 换 内 容 代
13、 替将 查 找 内 容 用 替 换 内 容 代 替 ( r e s u l t = ( r e s u l t = result+Text3.Text);result+Text3.Text);替换次数计数替换次数计数(count=count+1);(count=count+1);记录起始位置记录起始位置i(posi(pos= =pos+Str(ipos+Str(i),),添加在字符串添加在字符串pospos中中););查找位置从当前位置前进查找位置从当前位置前进Len(Text1.Text)Len(Text1.Text)个位置个位置(i=i+Len(Text1.Text)(i=i+Len(Te
14、xt1.Text)。否则。否则, ,将当前位置上的字将当前位置上的字符 添 加 到 字 符 串符 添 加 到 字 符 串 r e s u l tr e s u l t 中中 , , 因 此因 此 ( 2 )( 2 ) 处 语 句 修 改 为处 语 句 修 改 为result=result+mid(Text1.Text,i,1)result=result+mid(Text1.Text,i,1)。答案答案: :(1)pos+Str(i)(1)pos+Str(i)(2)result=result+mid(Text1.Text,i,1)(2)result=result+mid(Text1.Text,i
15、,1)【典例典例3 3】某某8 8位男生的肺活量数据放在数组元素位男生的肺活量数据放在数组元素a(1)a(1)到到a(8)a(8)中中, ,其数据依次其数据依次为为“3104,3700,3058, 3222,3621,3329,4233,4540”3104,3700,3058, 3222,3621,3329,4233,4540”。使用顺序查找算法。使用顺序查找算法查找数据查找数据3339,3339,则共需查找次数为则共需查找次数为( () )A.0A.0B.1B.1C.8C.8D. 9D. 9解析解析: :本题考查的是顺序查找算法的实现过程。由于给定的数列中没有数据本题考查的是顺序查找算法的实
16、现过程。由于给定的数列中没有数据3339,3339,因此需要与数列中每个数进行比较因此需要与数列中每个数进行比较, ,全部比较完后才知道查找失败全部比较完后才知道查找失败, ,因因此共需查找次数为此共需查找次数为8 8次。次。答案答案: :C C 考点考点2 2 对分查找对分查找 1.1.对分查找的基本思想对分查找的基本思想在有序的数据序列中在有序的数据序列中( (一般存放在数组中一般存放在数组中),),首先把要查找的数据与数组中间位首先把要查找的数据与数组中间位置的元素进行比较置的元素进行比较, ,如果相等如果相等, ,则查找成功并退出查找则查找成功并退出查找; ;否则否则, ,根据数组元素
17、的有根据数组元素的有序性序性, ,确定数据应在数组的前半部分还是在后半部分查找确定数据应在数组的前半部分还是在后半部分查找; ;在确定了新的查找范在确定了新的查找范围后围后, ,重复进行以上比较重复进行以上比较, ,直到找到或未找到为止。直到找到或未找到为止。重难点剖析重难点剖析对分查找的前提是被查找的数据序列必须是有序。对分查找的前提是被查找的数据序列必须是有序。“未找到未找到”是指当指定范围内的起点大于终点仍未找到该数据。是指当指定范围内的起点大于终点仍未找到该数据。2.2.对分查找算法基本框架对分查找算法基本框架说明说明: :要查找的数为要查找的数为key,key,待查找的数存放在数组待
18、查找的数存放在数组d d中。中。i i为查找范围的起点为查找范围的起点,j,j为查找范围的终点为查找范围的终点,m,m为范围为范围 i,ji,j 的中间位置。的中间位置。i=1i=1j=nj=nDo While i=jDo While ij,ij,则表示未找到则表示未找到3.3.对分查找程序实现对分查找程序实现在在n n个数组元素中依次查找个数组元素中依次查找, ,找到第找到第1 1个满足条件的值个满足条件的值, ,查找就结束查找就结束, ,输出找到输出找到元素所在的位置元素所在的位置; ;若找不到若找不到, ,输出输出“未找到未找到”。程序实现程序实现: :设要查找的数据是设要查找的数据是k
19、ey(key(在文本框在文本框Text1Text1中输入中输入),),查找的数据存放在数组查找的数据存放在数组d d中。中。在文本框在文本框Text2Text2中输出查找结果中输出查找结果, ,若找到输出若找到输出“找到找到! !位置为位置为:X”,:X”,否则输出否则输出“未找到未找到!”!”在文本框在文本框Text3Text3中输出共查找的次数。中输出共查找的次数。p p表示查找的次数。表示查找的次数。核心代码为核心代码为( (以升序为例以升序为例):):key = Val(Text1.Text)key = Val(Text1.Text)表示要查找的数表示要查找的数p=0p=0表示查找的次
20、数表示查找的次数find=Falsefind=False查找的结果查找的结果, ,若若find=Truefind=True表示找到表示找到,find=False,find=False表表示未找到示未找到i=1i=1查找范围的起点查找范围的起点j=nj=n查找范围的终点查找范围的终点Do While i=j And Not findDo While iIf keyd(md(m) Then) Then表示查找的数比中间位置上的数大时表示查找的数比中间位置上的数大时i=m+1i=m+1ElseElse表示查找的数比中间位置上的数小时表示查找的数比中间位置上的数小时j=m-1j=m-1EndIfEnd
21、IfLoopLoopIf Not find Then Text2.Text=If Not find Then Text2.Text=未找到未找到!Text3.Text=Text3.Text=共查找的次数为共查找的次数为:+:+Str(pStr(p) )重难点剖析重难点剖析计算中点位置的语句还可以写成计算中点位置的语句还可以写成:m=Int(i+j)/2):m=Int(i+j)/2)或或m=Fix(i+j)/2)m=Fix(i+j)/2)。 解析解析: :本题主要考查的是对分查找算法。在本题主要考查的是对分查找算法。在0,10,1区间内查找一个数区间内查找一个数, ,第一次第一次取取0,10,1
22、区间中间值区间中间值0.5,0.5,每次都减少为原来的每次都减少为原来的1/2,1/2,所以答案为所以答案为D D。答案答案: :D D 【典例典例4 4】已知单调函数在已知单调函数在0,10,1区间存在一个区间存在一个x x0 0, ,使使f(xf(x0 0)=0)=0。现用对分查找。现用对分查找算法搜索算法搜索x x0 0的值的值, ,开始搜索区间为开始搜索区间为0,1,0,1,若经过若经过1010次对分查找后还需继续搜次对分查找后还需继续搜索索, ,则第则第1111次搜索区间的长度为次搜索区间的长度为( () )A.1/2A.1/2 B.1/10 B.1/10C.1/10C.1/102
23、2D.1/2D.1/21010【典例典例5 5】( (20172017浙江浙江1111月选考月选考) )某算法的某算法的VBVB程序段如下程序段如下: :i = 1: j = 7: s = i = 1: j = 7: s = key = key = Int(RndInt(Rnd * * 100) 100)Do While i = jDo While i = jm = (i + j) 2m = (i + j) 2If key = If key = a(ma(m) Then) Thens = s + M: Exit Dos = s + M: Exit DoExit DoExit Do表示退出循环表
24、示退出循环ElseIfElseIf key key a(ma(m) Then) Thenj = m - 1: s = s + Lj = m - 1: s = s + LElseElsei = m + 1:s = s + Ri = m + 1:s = s + REnd IfEnd IfLoopLoopText1.Text = sText1.Text = s数组元素数组元素a(1)a(1)到到a(7)a(7)的值依次为的值依次为“24,35,38,41,45,69,78”24,35,38,41,45,69,78”。若该程序段执。若该程序段执行后行后, ,文本框文本框Text1Text1中显示的内容
25、可能是中显示的内容可能是( ( ) )A.RLA.RL B.LMR B.LMR C.RLR C.RLR D.LRLM D.LRLMC C解析解析: :本题主要考查的是对分查找算法。查找的结果有成功和不成功两种本题主要考查的是对分查找算法。查找的结果有成功和不成功两种, ,若若查找成功查找成功, ,则最后输出则最后输出M,M,如果查找不成功如果查找不成功, ,则不会出现则不会出现M,M,因此因此MM不可能不可能出现在中间出现在中间, ,故故B B选项错误。对选项错误。对 n n 个数据查找个数据查找, ,最多查找次数为最多查找次数为 loglog2 2 n+1( n+1(向向下取整下取整) ,7
26、 ) ,7 个元素最多查找个元素最多查找3 3次次, ,因此可排除因此可排除 D D 选项。如果查找失败选项。如果查找失败, ,则需则需要查找要查找3 3次次, ,即不可能查找即不可能查找2 2次就结束次就结束, ,因此因此 A A 选项也错误。故答案为选项也错误。故答案为 C C。 【典例典例6 6】( (20172017浙江省浙江省4 4月选考月选考) )某对分查找算法的某对分查找算法的VBVB程序段如下程序段如下: :Key = Val(Text1.Text)Key = Val(Text1.Text)i = 1: j = 10i = 1: j = 10Text2.Text = Text2
27、.Text = Do While i =jDo While i =jm=m=Int(i+jInt(i+j) / 2+0.5) / 2+0.5)If Key=If Key=a(ma(m) Then Exit Do) Then Exit Do Exit DoExit Do表示退出循环表示退出循环If KeyIf Keya(ma(m) Then j=m - 1 Else i=m+1) Then j=m - 1 Else i=m+1Text2.Text = Text2.Text+Str(a(m)Text2.Text = Text2.Text+Str(a(m)LoopLoop数组元素数组元素a(1)a(
28、1)到到a(10)a(10)的值依次为的值依次为“8,17,24,30,36,40,55,58,61,66”,8,17,24,30,36,40,55,58,61,66”,文本框文本框Text1Text1中输入的值是中输入的值是30,30,执行该程序段执行该程序段, ,文本框文本框Text2Text2中显示的是中显示的是( () )A.40A.402424B.40B.4024243636C.36C.362424D.36D.3617172424解析解析: :本题主要考查对分查找代码执行过程。具体查找过程如表所示本题主要考查对分查找代码执行过程。具体查找过程如表所示: :Key=30Key=30由此
29、可知由此可知, ,共查找了共查找了4 4次次, ,最后一次满足最后一次满足Key=Key=a(ma(m),),执行执行Exit DoExit Do退出循环退出循环, ,其其他几次的他几次的a(ma(m) )按次序依次显示在按次序依次显示在Text2Text2中。中。答案答案: :B B 查找次数查找次数i ij jm= m= Int(i+j)/2+0.5)Int(i+j)/2+0.5)a(ma(m) )比较结果比较结果1 11 110106 64040KeyKeyKeya(ma(m) )3 34 45 55 53636KeyKey 0 ThenIf pos 0 ThenLabel4.Capti
30、on = Label4.Caption = b(pos)+c(posb(pos)+c(pos) )ElseElseLabel4.Caption = Label4.Caption = 找不到此学号找不到此学号!End IfEnd IfEnd SubEnd SubFunction Function Search(KeySearch(Key As String) As Integer As String) As IntegerDim i As Integer, j As Integer, m As IntegerDim i As Integer, j As Integer, m As Integer
31、i = 1:j = ni = 1:j = nDo While i = jDo While i 0 Then”“If pos0 Then”可可知知, ,将函数的返回值保存在变量将函数的返回值保存在变量pospos中中, ,因此划线处的代码为因此划线处的代码为pos = pos = Search(x);Search(x);函数的函数值是通过函数名来返回的函数的函数值是通过函数名来返回的, ,划线处表示找到的情划线处表示找到的情况况, ,因此将返回该学号在数组因此将返回该学号在数组a a中的位置中的位置m,m,即划线处代码为即划线处代码为Search=m;Search=m;数数据已按学号升序排序据已
32、按学号升序排序, ,根据代码根据代码“j=m-1”“j=m-1”可知可知, ,划线处代码表示学号小划线处代码表示学号小于于a(m)a(m)的情况的情况, ,因此处代码为因此处代码为a(m)Keya(m)Key。答案答案: :pos=pos=Search(xSearch(x) )Search=mSearch=ma(ma(m)Key )Key 【典例典例8 8】编写编写VBVB程序程序, ,实现如下功能实现如下功能: :在文本框在文本框Text1Text1中输入一个整数中输入一个整数, , 单击单击“查找删除查找删除”按钮按钮Command1,Command1,采用对分查找法在数组采用对分查找法在
33、数组A(A(从小到大排列从小到大排列, ,并显示并显示在标签在标签Label1Label1中中) )中查找该数。若找到中查找该数。若找到, ,则从数组则从数组A A中删除该数中删除该数( (该数后面的数该数后面的数组元素都前移一位组元素都前移一位),),并在标签并在标签Label2Label2中显示删除后的结果中显示删除后的结果, ,否则否则, ,在标签在标签Label2Label2中显示中显示“该数没有找到该数没有找到”。程序运行效果如图。程序运行效果如图4-3-34-3-3所示。所示。实现上述功能的实现上述功能的VBVB代码如下代码如下, ,但加框处代码有错但加框处代码有错, , 请改正。
34、请改正。Dim A(1 To 10) As Integer Dim A(1 To 10) As Integer 用于保存用于保存1010个按从小到大顺序排列的整数个按从小到大顺序排列的整数Form_LoadForm_Load 事件过程产生事件过程产生1010个整数个整数, , 按升序保存在数组按升序保存在数组A A中中, , 并在标签并在标签Label1Label1中中显示显示Private Sub Private Sub Form_LoadForm_Load()()代码略代码略End SubEnd SubPrivate Sub Command1_Click()Private Sub Comm
35、and1_Click()Dim i As Dim i As Integer,jInteger,j As As Integer,mInteger,m As Integer, k As Integer As Integer, k As IntegerDim x As Integer, f As Boolean Dim x As Integer, f As Boolean 变量变量 f f 用于标记是否在数组中找到用于标记是否在数组中找到 x xx= Val(Text1.Text)x= Val(Text1.Text)i=1:j=10i=1:j=10f=Falsef=FalseDo While i=j
36、 And f=FalseDo While ix Then i=m +1 Else j=m -1 (1)x Then i=m +1 Else j=m -1 (1)LoopLoopIf f=True ThenIf f=True ThenFor k=m To 9For k=m To 9a(k+1)=a(k+1)=a(ka(k) )Next kNext kLabel2.Caption= Label2.Caption= 解析解析: :本题考查的是对分查找的程序实现。给定的数据是按从小到大排序本题考查的是对分查找的程序实现。给定的数据是按从小到大排序的的, ,因此如果要查找的数比中间位置上的数大因此如果要
37、查找的数比中间位置上的数大, ,则到后半部分找则到后半部分找, ,即即i=m+1,i=m+1,否则在前半部分找否则在前半部分找, ,即即j=m-1,j=m-1,因此因此(1)(1)处语句应改为处语句应改为a(ma(m)x)xa(ma(m) )。若找。若找到到, ,则从数组则从数组A A中删除该数中删除该数, ,即该数后面的数组元素都前移一位即该数后面的数组元素都前移一位, ,因此因此(2)(2)处处语句应改为语句应改为a(ka(k)=a(k+1)=a(k+1)。答案答案: :(1)a(m)x (1)a(m)a(m) (2)a(k)=a(k+1)xa(m) (2)a(k)=a(k+1) For k=1 To 9For k=1 To 9Label2.Caption=Label2.Caption+Str(a(k)+ Label2.Caption=Label2.Caption+Str(a(k)+ Next kNext kElseElseLabel2.Caption=Label2.Caption=该数没有找到该数没有找到EndIfEndIfEnd SubEnd Sub点击进入点击进入 课时训练课时训练
