第4节 查找算法
考试内容 考试要求
顺序查找算法思想及程序实现 c
对分查找算法思想及其变形的程序实现 c
一、顺序查找算法思想和程序实现
顺序查找的基本思想是从第一个数据开始，按顺序逐个将数据与给定的数据(查找键)进行比较，若某个数据和查找键相等，则查找成功，输出所查数据的位置；反之，输出未找到。
For i ＝ 1 To n If a(i)＝key Then Exit For End If Next i 代码分析：将数组中的每个元素逐个与key进行比较，如果相等则查找成功，循环结束。如果循环结束后，变量i的值等于n＋1，则意味着没有找到。顺序查找数组可以无序
二、对分查找算法思想
对分查找又称二分查找，是一种高效的查找方法。对分查找的前提是被查找的数据是有序的(升序或降序)。对分查找的基本思想是在有序的数列中，首先将要查找的数据与有序数列内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则就根据数据的有序性，再确定该数据的范围应该在数列的前半部分还是后半部分；在新确定的缩小范围内，继续按上述方法进行查找，直到找到要查找的数据，即查找成功，如果要查找的数据不存在，即查找不成功。
若key为查找关键字，数组d存放n个已按升序排序的数据。使用对分查找时，把查找范围[i，j]的中间位置上的数据d(m)与key进行比较，结果必然是如下三种情况之一：
(1)若key
(2)key＝d(m)，找到了需要的数据；
(3)key>d(m)，查找键大于中点d(m)处的数据。由数组d中的数据的递减性，可以确定：在(i, m)内不可能存在值为key的数据，必须在新的范围(m＋1，j)中继续查找。
这样，除了出现情况(2)，在通过一次比较后，新的查找范围将不超过上次查找范围的一半。
数组d为例，观察对分查找的过程。要查找的数据key＝52，查找过程如下：
三、对分查找算法代码实现
i ＝ 1: j ＝ n: s ＝ 0 Do While i <＝ j m ＝ (i ＋ j) \ 2 If a(m) ＝ key Then s ＝ m: Exit Do ElseIf key < a(m) Then j ＝ m － 1 Else i ＝ m ＋ 1 End If Loop 左边程序实现在升序数组a(1)…a(n)中查找值等于key的元素，将其下标存储在s中。如果没有找到则s值为0，如果找到，则s存储对应元素的下标。 对分查找前提是数据有序，对n个数据查找，最多查找次数为Log2n＋1(向下取整)。 例如在有序数组a(1)…a(10000)中查找某个值，最多需要查找Log210000＋1，即14次
一、顺序查找算法思想和代码实现
【典例1】 小王拿着一大串钥匙去开仓库的某一扇门，由于钥匙上没有任何标记，小王只能将这一串钥匙一把一把地去试，从算法角度看，小王的做法属于( )
A.冒泡排序 B.选择排序
C.对分查找 D.顺序查找
解析 本题考查两个算法的区别。顺序查找的思想第从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较，若某个数据与给定的值相等，则查找成功，否则查找不成功。
答案 D
【变式训练】 用对分查找法和顺序查找法在数字序列“1，2，3，5，8，13，21，34，55”中查找数字13，两种方法都能访问到的数字是( )
A.3 B.5
C.8 D.34
解析 对分查找访问到的数字为8、21、13，顺序查找访问到的数字为1，2，3，5，8，13。两者共同为8。
答案 C
二、对分查找算法思想
【典例2】 已知单调函数f(x)在[0，1]区间存在一个x0，使f(x0)＝0。现用对分查找法搜索x0的值，开始搜索区间为[0，1]，若经过10次对分查找后还需继续搜索，则第11次搜索区间的长度为( )
A.1/2 B.1/10
C.1/102 D.1/210
解析 对分查找的每次区间变为上次的二分之一。第2次为原搜索区间的长度1/2，第3次为原搜索区间的长度1/4……第11次为原搜索区间的长度1/210，所以答案D。
答案 D
【变式训练】 下列有关查找的说法，正确的是( )
A.进行对分查找时，被查找的数据必须已按升序排列
B.进行对分查找时，如果查找的数据不存在，则无需输出结果
C.在新华字典中查找某个汉字，最适合使用顺序查找
D.对规模为n的数据进行顺序查找，平均查找次数是
解析 对分查找的前提是被查找的数据是有序的(升序或降序)。如果找不到，程序应该要输出未找到的相关提示信息。在新华字典中查找某个汉字，不适合使用顺序查找，适合使用对分查找。对规模为n的数据进行顺序查找，最少查找1次，最多查找n次，平均查找次数是。
答案 D
【典例3】 数组变量d(1)到d(8)的值依次为97、86、79、68、56、41、33、13，用“对分查找”找到“13”的过程中，依次被访问到的数据是( )
A.68、13 B.68、41、13
C.56、41、33、13 D.68、41、33、13
解析 本题考查标准的对分查找，查找中间项为m＝(i＋j)\2，经过4次对分查找。
i 1 5 7 8
j 8 8 8 8
m 4 6 7 8
d(m) 68 41 33 13
答案 D
【变式训练】 在有序单词序列“bike，cake，data，easy，feel，great，hive，mark，sweet”中，用对分查找算法找到“easy”过程中，依次被访问到的数据为( )
A.feel, data, easy
B.great, data, easy
C.bike, cake, dada，easy
D.feel，cake，data，easy
解析 本题考查标准的对分查找，查找中间项为m＝(i＋j)\2，经过4次对分查找。
i 1 1 3 4
j 9 4 4 4
m 5 2 3 4
d(m) feel cake data easy
答案 D
三、对分查找算法代码实现
【典例4】 某对分査找算法的VB程序段如下：
i ＝ 1: j ＝ 9: n ＝ 0
key ＝ Val(Text1.Text)
Do While i <＝ j
n ＝ n ＋ 1
m ＝ Fix((i ＋ j) / 2)
If key ＝ d(m) Then Exit Do ′Exit Do表示退出循环
If key < d(m) Then j ＝ m － 1 Else i ＝ m ＋ 1
Loop
数组元素d(1)到d(9)的值依次为“7，12，18，25，39，58，61，72，86”。若该程序段运行结束后，n的值为2，则key的值是( )
A.39 B.18或61
C.18或72 D.12或61
解析 n代表查找次数，代入选项计算查找次数为2，即为答案。key＝12，第1次：m＝5，i＝1，j＝4；第2次：m＝2 ，d(m)＝12查找成功。key＝61，第1次：m＝5，i＝6，j＝9；第2次：m＝7 ，d(m)＝61查找成功。所以答案选D。
答案 D
【变式训练】 采用如下对分查找算法对数组a中7个有序数据“15，38，51，66，77，81，99”进行查找，查找数据为“55”，
i ＝ 1: j ＝ 7: x ＝ 55
Do While i <＝ j
m ＝ (i ＋ j) \ 2
If a(m) ＝ x Then Exit Do
If a(m) > x Then j ＝ m － 1 Else i ＝ m ＋ 1
Loop
执行完上述代码后，根据最终变量值判断下列表达式，其中正确的是( )
A.i＝m＋1 B.i＝m－1
C.j>m＋1 D.j解析 本题考查标准的对分查找，查找中间项为m＝(i＋j)\2，最终没有找到该数据。算法结束时i＝4，j＝3，m＝3，所以答案选A。
i 1 1 3 4
j 7 3 3 3
m 4 2 3
d(m) 66 38 51
答案 A
【典例5】 有如下VB程序段：
i ＝ 1 : j ＝ 10 : flag ＝ True : n ＝ 0
Key ＝ Val(Text1.Text)
Do While i <＝ j And flag ＝ True
m ＝ (i ＋ j) \ 2
If a(m) ＝ Key Then
flag ＝ False
ElseIf a(m) > Key Then
i ＝ m ＋ 1 : n ＝ n － 1
Else
j ＝ m － 1 : n ＝ n ＋ 1
End If
Loop
数组元素a(1)到a(10)依次是99, 94, 90, 87, 70，69，60，56，45，36，变量n的值最终是0，则文本框Text1输入的数字可能是( )
A.100 B.87
C.69 D.41
解析 本题考查的是对分查找的变形。当key＝100时，程序执行过程中，各个变量的值变化情况如下表所示：
i 1 1 1 1
j 10 4 1 0
m 5 2 1
d(m) 70 94 99
n 1 2 3
当key＝87时，程序执行过程中，各个变量的值变化情况如下表所示：
i 1 1 3 4
j 10 4 4 4
m 5 2 3 4
d(m) 70 94 90 87
n 1 0 －1
当key＝69时，程序执行过程中，各个变量的值变化情况如下表所示：
i 1 6 6
j 10 10 7
m 5 8 6
d(m) 70 56 69
n －1 0
当key＝41时，程序执行过程中，各个变量的值变化情况如表所示。
i 1 6 9 10 10
j 10 10 10 10 9
m 5 8 9 10
d(m) 70 56 45 36
n －1 －2 －3 －2
答案 C
【变式训练】 有如下VB程序段：
i ＝ 1: j ＝ 9: f ＝ False
Do While i <＝ j And Not f
m ＝ Fix((i ＋ j) / 2)
If a(m) ＝ Key Then
p ＝ m : f ＝ True
End If
If a(m) > Key Then
j ＝ m － 1
Else
i ＝ m ＋ 1
End If
Loop
If f ＝ True Then
Text1.Text＝“数据位置：” ＋ Str(p)
Else
Text1.Text＝“没有找到该数据！”
End If
数组元素a(1)到a(9)的值依次为10，15，30，32，38，42，45，48，68，若通过如下程序段查找数据key＝43，则在执行该程序段的过程中，依次访问的数据是( )
A.38，45，42 B. 38，45，48
C.38，48，42 D. 38，48，45
解析 本题考查的是对分查找的变形。在程序执行过程中，各个变量的值变化情况如下表所示，所以答案选A。
i 1 6 6
j 9 9 6
m 5 7 6
d(m) 38 45 42
答案 A
【典例6】 小明为了研究对分查找的过程中数据被访问的情况，编写了一个VB程序，功能如下：在列表框List1中显示已经排序的数据(存储在数组a中)，在文本框Text1中输入要查找的数据，单击“查找”按钮Command1后，在标签Label1中显示查找中依次被访问到的数据。程序运行界面如图所示。
实现上述功能的VB程序如下，但加框处代码有错，请改正。
Const n ＝ 10
Dim a(1 To n) As Integer
Dim s As String
Private Sub Form_Load()
′产生随机数依次存储在数组a中，代码略
′对数组a升序排序并在列表框输出，代码略
End Sub
Private Sub Command1_Click()
Dim x As Integer, p As Integer
x ＝ Val(Text1.Text)
s ＝ “ ”
′(1)
If p > 0 Then s ＝ s ＋ “查找成功” Else s ＝ s ＋ “查找失败”
Label1.Caption ＝ “依次被访问的数据为：” ＋ s
End Sub
Function search(key As Integer) As Integer
Dim i As Integer, j As Integer, flag As Boolean
flag ＝ False
i ＝ 1: j ＝ n: search ＝ 0
Do While i <＝ j And Not flag
m ＝ (i ＋ j) \ 2
If a(m) ＝ key Then
search ＝ m
flag ＝ True
′(2)
j ＝ m － 1
Else
i ＝ m ＋ 1
End If
s ＝ s ＋ Str(a(m)) ＋ “→”
Loop
End Function
程序中加框(1)处应改正为_________________________________________；
加框(2)处应改正为________________________________________________。
解析 (1)联系下文代码If p > 0 Then，需要对变量p赋值，结合函数search的功能：如果在数组a中找到要查找的数，函数search 返回该数在数组中的位置，如果没有找到，函数search 返回值为0，结合程序得知第1空为：p＝search(x)。
(2)在一个块If语句中结合对分查找算法得出第2空为： ElseIf Key < a(m) Then。
答案 (1)p＝search(x) (2)ElseIf Key < a(m) Then
1.某数组有10个元素，依次为：5，12，16，23，27，30，35，41，49，50。下列说法正确的是( )
A.使用对分查找数据12，需要的查找次是3次
B.使用顺序查找数据50，需要的查找次数是9次
C.使用对分查找数据41，需要的查找次数是2次
D.使用顺序查找数据5，需要的查找次数是0次
解析 本题考查标准的对分查找，查找中间项为m＝(i＋j)\2，查找12的过程如下表所示。故查找12需要2次。
i 1 1
j 10 4
m 5 2
d(m) 27 12
顺序查找数据50，需要的查找次数是10次，
查找41的过程如下表所示，故查找41需要4次。
i 1 6
j 10 10
m 5 8
d(m) 27 41
顺序查找5需要1次。
答案 C
2.某对分查找算法的VB程序段如下：
i＝1：j＝7：n＝0：f＝False
Key＝Val(Text1.Text)
Do While i<＝j And f＝False
n＝n＋1
m ＝ Fix((i ＋ j) / 2)
If Key＝d(m) Then f＝True
If KeyLoop
元素d(1)到d(7)的值依次是“10，20，30，40，50，60，70”，文本框Text1中输入35后运行程序段，运行结束后下列说法正确的是( )
A.变量f的值是True B.变量i的值是4
C.变量m的值是3.5 D.变量n的值是4
解析 本题考查的是对分查找的变形。在程序执行过程中，各个变量的值变化情况如下表所示：
i 1 1 3 4
j 7 3 3 3
n 1 2 3
m 4 2 3
f false false false
d(m) 40 20 30
程序执行后，变量i＝4，变量j＝3，变量n＝3，变量m＝3，变量f＝false。
答案 B
3.某对分查找算法的VB程序段如下：
n ＝ 0: i ＝1: j ＝6
Key ＝ Val(Text1.Text)
f ＝ False
Do While i < ＝ j And Not f
m ＝ (i ＋ j ＋1) \ 2
n ＝ n ＋ 1
If Key ＝ d (m) Then
f ＝ True
ElseIf Key > d(m) Then
j＝m－1
Else
i＝m＋1
End If
Loop
数组元素d(1)到d(6)的值依次为“87，72，53，41，29，18”，若该程序段运行后，n的值为2，则key的值是( )
A.87或29 B.72或18
C.72或29 D.53或18
解析 本题考查对分查找的变形，n代表查找次数，n＝2代表查找次数是2次。第一次查找：i＝1，j＝6，m＝4，d(m)＝41。第二次查找分为两种情况，第一种情况是key<41，i＝1，j＝3，m＝2，d(m)＝72；第二种情况是key>41，i＝5，j＝6，m＝6，d(m)＝18，所以答案是B。
答案 B
4.某对分査找算法的VB程序段如下：
i ＝ 1: j ＝ 7: s ＝ “ ”
key ＝ Int(Rnd * 100)
Do While i <＝ j
m ＝ (i ＋ j) \ 2
If key ＝ a(m) Then
s ＝ s ＋ “M”： Exit Do ′Exit Do 表示退出循环
ElseIf key < a(m) Then
j ＝ m － 1: s ＝ s ＋ “L”
Else
i ＝ m ＋ 1: s ＝ s ＋ “R”
End If
Loop
Text1.Text ＝ s
数组元素a(1)到a(7)的值依次为“24，35，38，41，45，69，78”。若该程序段执行后，文本框Text1中显示的内容可能是( )
A.RL B.LMR
C.RLR D.LRLM
解析 本题主要考查对分查找的变形和查找次数，最简单的方法是使用排除法。分析程序可知，查找成功则会输出“M”，循环结束，所以“M”不可能出现在中间，排除B选项。对于n个数据查找，最多的查找次数是Log2n＋1(向下取整)，7个元素最多只需要查找3次，所以排除D选项，如果无法找到数据，则不会输出“M”，则需要查找的次数是3次，所以排除A选项。
答案 C
5.数组a中有100个正整数，已按升序排列。在文本框Text1中输入一个正整数key，寻找数组a中是否有一对数的和等于给定的数key。若存在和为key的数对，输出该数对包含的两个整数，小的在前，大的在后。若有多个数对满足条件，则输出最先找到的数若找不到符合要求的数对，则输出“没有符合条件的数对”。小吴为此编写了VB程序，代码如下，但加框处代码有错，请改正。
Dim a(1 To 100) As Integer
Const n ＝ 100
Private Sub Command1_C1ick()
Dim key As Integer, left As Integer, right As Integer, mid As Integer
Dim flag As Boolean
flag ＝ False: key ＝ Val(Text1.Text)
For i ＝ 1 To n － 1
′①
right ＝ n
Do While ′②
mid ＝ (left ＋ right)\2
If a(i)＋a(mid) < key Then
left ＝ mid ＋ 1
ElseIf a(i)＋a(mid) > key Then
right ＝ mid－1
Else
List1.AddItem Str(a(i)) & “ ” & Str(a(mid))
flag ＝ True
End If
Loop
Next i
If Not flag Then Listl.AddItem “没有符合条件的数对”
End Sub
程序中加框①处应改正为____________________________________________；
加框②处应改正为___________________________________________________。
解析 i＝1时，从a(2)到a(100)里面查找a(mid)，使a(1)＋a(mid)等于key。在a(2)到a(50)之间采用对分查找如果找到，输出，Flag变为True，循环结束。否则继续……i＝2时，从a(3)到a(50)里面查找a(mid)，使a(2)＋a(mid)等于key。
答案 ①left＝i＋1 ②left<＝right And Not Flag
基础巩固
1.下列关于数列查找说法，正确的是( )
A.使用对分查找，数列中每个元素对象不能是字符串类型的数据
B.使用对分查找数列，数列中每个元素要求必须是经过排序的
C.对于规模为1000万项数的数列，不能使用顺序查找
D.使用顺序查找，只能从第1个元素依次向后进行查找
解析 对分查找的前提是被查找的数据是有序的(升序或降序)，数据类型可以使数字类型也可以是字符串类型。顺序查找可以从第一个数据依次往后查找，也可以从最后一个数据依次向前查找。
答案 B
2.某对分査找算法的VB程序段如下：
i ＝ 1: j ＝ 9: f ＝ False
Do While i <＝ j And Not f
m ＝ Fix((i ＋ j) / 2)
If a(m) ＝ Key Then
p ＝ m : f ＝ True
End If
If a(m) > Key Then
j ＝ m － 1
Else
i ＝ m ＋ 1
End If
Loop
If f ＝ True Then
Text1.Text＝“数据位置：” ＋ Str(p)
Else
Text1.Text＝“没有找到该数据！”
End If
数组元素a(1)到a(9)的值依次为10，15，30，32，38，42，45，48，68，若通过如下程序段查找数据key＝43，则在执行该程序段的过程中，依次访问的数据是( )
A.38，45，42 B.38，45，48
C.38，48，42 D.38，48，45
解析 本题考查的是对分查找的变形。在程序执行过程中，各个变量的值变化情况如下表所示，所以答案选A。
i 1 6 6 7
j 9 9 6 6
m 5 7 6
a(m) 38 45 42
答案 A
3.某对分査找算法的VB程序段如下：
Key ＝ Val(Text1.Text)
i ＝ 1: j ＝ 10：Text2.Text＝“ ”
Do While i <＝ j
m＝(i＋j＋1)\2
If key ＝ a(m) Then Exit Do
If key > a(m) Then j＝m－1 Else i＝m＋1
Text2.Text＝Text2.Text＋Str(a(m))
Loop
已知数组 a(1 To 10)中的数据分别是83、80、66、46、44、36、21、16、15、12，在文本框Text1中输入80，执行该程序段，文本框Text2中显示的是( )
A.36 66 B.44 88
C.36 46 D.44 66
解析 本题考查的是对分查找的变形。在程序执行过程中，各个变量的值变化情况如下表所示，所以答案是A。
i 1 1 1
j 10 5 2
m 6 3 2
a(m) 36 66 80
答案 A
4.某对分查找算法的VB程序段如下：
Key ＝ Val(Text1.Text) Mod 10
Text2.Text ＝ “ ”
i ＝ 1: j ＝ 10: f ＝ False
Do While i <＝ j And Not f
m ＝ (i ＋ j) \ 2
If a(m) \ 10 ＝ Key Then
search ＝ m：f ＝ True
ElseIf a(m) \ 10 < Key Then
i ＝ m ＋ 1
Else
j ＝ m － 1
End If
Text2.Text ＝ Str(m) ＋ Text2.Text
Loop
数组元素a(1)到a(10)的值依次为：8，15，19，23，35，37，42，48，55，68，文本框Text1中输入21，执行该程序段，文本框Text2中显示的是( )
A.5 2 B.2 5
C.15 35 D.35 15
解析 本题考查的是对分查找的变形。Key＝1，在程序执行过程中，各个变量的值变化情况如下表所示，所以答案是B。
i 1 1
j 10 4
m 5 2
a(m) 35 15
a(m)\10 3 1
答案 B
能力提升
5.已知一无序数组a(下标1到n)，通过引入数组b(下标1到n)，使得a(b(1))≤a(b(2)) ≤a(b(3))……≤a(b(n))(示例如图所示)，对这些有序数据可进行对分查找。则第一次查找时，中点位置m与中点值分别是( )
A.m的值是Fix((1＋n)/2)，中点值是 a(m)
B.m的值是Fix((1＋n)/2)，中点值是 a(b(m))
C.m的值是Fix((b(1))＋b(n))/2)，中点值是 a(m)
D.m的值是Fix((b(1))＋b(n))/2)，中点值是 a(b(m))
解析 对分查找的数组必须有序，数组a(i)是无序的无法对分查找，但a(b(i))是有序的可以对分查找。第一次查找时，有序数组a(b(i))的中点数据为a(b(3))，也就是m＝3。所以答案是B。
答案 B
6.有如下VB程序段：
Key ＝ Val(Text1. Text)
i ＝ 1: j ＝ 10
flag ＝ False
s ＝“ ”
Do While i <＝ j And Not flag
mid1 ＝ Int(i ＋ (j － i) / 3)
mid2 ＝ Int(j － (j － i) / 3)
If Key ＝ a (mid1) Then
flag ＝ True
ElseIf Key j ＝ mid1 － 1
ElseIf Key ＝ a(mid2) Then
flag ＝ True
ElseIf Key >a(mid2) Then
i ＝ mid2 ＋ 1
Else
i ＝ mid1 ＋ 1 ：j ＝ mid2 － 1
End If
s ＝ s & “ ” & mid1 & “：” & mid2
Loop
Text2.Text ＝ s
已知数组 a(1 To 10)中的数据分别是 12、21、34、45、59、63、72、86、94、100，在文本框Text1中输入34，程序运行后文本框Text2 中显示的内容是( )
A.4：7 1：2 B.4：7 1：2 3：3
C.4：7 1：3 3：3 D.4：7 3：3
解析 本题考查的是对分查找的变形。在程序执行过程中，各个变量的值变化情况如下表所示，所以答案选B。
i 1 1 3
j 10 3 3
mid1 4 1 3
mid2 7 2 3
a(mid1) 45 12 34
a(mid2) 72 21 34
答案 B
7.利用对分査找算法计算整数勾股数对的VB程序段如下：
flag ＝ True : p ＝ 0
Key ＝ 5
For i ＝ 1 To Key － 1
L ＝ i ＋ 1: R ＝ Key － 1
Do While L <＝ R And flag
M ＝ (L ＋ R) \'2
p ＝ p ＋ 1
If i * i ＋ M * M < Key * Key Then
L ＝ M ＋ 1
ElseIf i * i ＋ M * M > Key * Key Then
R ＝ M － 1
Else
Text2.Text ＝ Str(i) ＋ “ ”＋Str(M) ＋ “ ” ＋ Str(key)
flag ＝ False
i ＝ Key
End If
Loop
Next i
If flag Then Text2.Text ＝ “没有符合条件的整数勾股数对！”
程序运行后，变量p的值为( )
A.3 B.4
C.5 D.6
解析 采用分类讨论的方法。当i＝1时，m＝3、4循环2次，i＝2时，m＝3、4循环2次，i＝3时，m＝4循环1次，找到Key为5，符合条件，共循环5次。
答案 C
8.数组元素a(0)到a(9)的值依次为“13，20，22，25，30，33，40，52，65，100”，文本框Text1中输入的值是33，执行该程序段，下列描述正确的是( )
key ＝ Val(Text1.Text)
i ＝ 0: j ＝ 9： s ＝ 0
Do While i <＝ j
m ＝ Fix((i ＋ j) \ 2 ＋ 0.5)
s ＝ s ＋ 1
If key ＝ a(m) Then
Label1.Caption ＝ Label1.Caption ＋ “→” ＋ Str(m)
Exit Do ′Exit Do表示退出循环
End If
If key < a(m) Then j ＝ m － 1 Else i ＝ m ＋ 1
Label1.Caption ＝ Label1.Caption ＋ “→” ＋ Str(m)
Loop
Label2.Caption ＝ “历经” ＋ CStr(s) ＋ “步”
A.标签Label1显示内容为“→4→7→5”
B.标签Label2显示内容为“历经1步”
C.该程序为顺序查找，查找次数为3
D.该程序为对分查找，查找次数为4
解析 本题考查的是对分查找的变形。在程序执行过程中，各个变量的值变化情况如下表所示，标签Label1显示内容为“→4→7→5”，标签Label2显示内容为“历经3步”，该程序为对分查找，查找次数为3，故答案是A。
i 0 5 5
j 9 9 6
m 4 7 5
a(m) 30 52 33
答案 A
9.小王编写了一个实现文字查找替换功能的VB程序，运行界面如图所示。文本框Text1显示原文内容，Text2中输入查找内容，Text3中输入替换内容，单击“全部替换”按钮Command1后，Text4显示查找替换的结果，Text5中显示替换的次数，Text6显示“查找内容”在原文中的起始位置。
实现上述功能的VB程序如下，但加框处代码有错，请改正。
Private Sub Command1_Click()
Dim s As String, result As String, pos As String
Dim count As Integer, i As Integer
i ＝ 1: count ＝ 0
result ＝ “ ”： pos ＝ “ ”
Do While i <＝ Len(Text1.Text)
s ＝ Mid(Text1.Text, i, Len(Text2.Text))
If s ＝ Text2.Text Then
result ＝ result ＋ Text3.Text
count ＝ count ＋ 1
pos ＝ ′①
i ＝ i ＋ Len(Text2.Text)
Else
′②
i ＝ i ＋ 1
End If
Loop
Text4.Text ＝ result
Text5.Text ＝ Str(count)
Text6.Text ＝ pos
End Sub
程序中加框①处应改正为____________________________________________；
加框②处应改正为________________________________________________。
解析 ①变量result存储替换后的新字符串，count存储替换次数，pos存储替换位置。程序通过变量i来读取原字符串中的字符，因此当前的位置是i。
②Else语句对应的情况是：原字符串中取出来的子串不等于替换内容，因此不需要替换，保持原样，从该行代码紧接着“i＝i＋1”可得出字符串往后移动一位，因此result需要保存原字符串当前位置i上的一个字符。
答案 ①pos＋Str(i) ②result＝result＋Mid(Text1.Text，i，1)
10.某校季运动会共n名运动员参赛，小明编写了根据号码牌查询学生信息的软件，输入号码牌就能查询该号码牌所属的班级和选手姓名。数组a、b、c分别保存了本次运动会所有选手的号码牌、班级、姓名的信息。第i个选手的号码牌保存在a(i)中，对应的班级和姓名保存在b(i)和c(i)中。程序界面如图所示，在文本框Text1中输入号码牌，单击“查询”按钮(Command1)，如果找到对应的信息，就显示所属班级和选手姓名，如果没有找到，则显示“未找到”。
(1)分析程序，可知数据库的文件名为__________，当前数据表的名称为：________。
(2)填入适当的语句和代码，把程序补充完整。
Dim n As Integer ′用于存储运动员总人数
Dim a(1000) As Integer, b(1000) As String，c(1000) As String
Private Sub Form_Load()
Dim conn As New ADODB.Connection
Dim rs As New ADODB.Recordset
conn.ConnectionString ＝ “Provider ＝ Microsoft.Jet.OLEDB.4.0；DATA Source＝” & App.Path & “\sport.accdb”
conn.Open
Set rs.ActiveConnection ＝ conn
rs.Open “号码牌”
n ＝ 0
Do While Not rs.EOF ′到记录集rs的最后一条记录后退出循环
n ＝ n ＋ 1
a(n) ＝ rs.Fields(“号码”) ′读取当前记录“号码”字段值
b(n) ＝ ____①____ ′读取当前记录“班级”字段值
c(n) ＝ rs.Fields(“姓名”) ′读取当前记录“姓名”字段值
____②____ ′移动到下一条记录
Loop
′按号码牌升序排序后，显示在列表框List1中
′其他代码略。
End Sub
Private Sub Command1_Click()
Dim x As Integer
x ＝ Val(Text1.Text)
pos ＝ ______③______
If pos > 0 Then
Text2.Text ＝ b(pos)：Text3.Text ＝ c(pos)
Else
Text2.Text ＝ “未找到”
End If
End Sub
Function Search(Key As Integer) As Integer
Dim i As Integer, j As Integer，
i ＝ 1：j ＝ n：Search ＝ 0
Do While i <＝ j
m ＝ Fix((i ＋ j) / 2)
If Key ＝ a(m) Then
Search ＝ m : Exit Function
ElseIf______④______ Then
j ＝ m － 1
Else
i ＝ m ＋ 1
End If
Loop
End Function
解析 (1)①根据数据文件名的扩展名accdb，在数据库连接代码中查找，即可找到sport.accdb。②代码rs.Open “号码牌”得知打开的是“号码牌”数据表。(2)①读取当前记录“班级”字段值到数组b中，即b(n)＝rs.Fields(“班级”)。②移动到下一条记录rs.MoveNext。③调用自定义函数，注意函数参数，将过程中x值传递给自定义函数中的key，即：Search(x)。函数的计算结果为数组中对应元素的下标，如果函数结果为0，意味着没有找到。 ④理解对分查找算法。
答案 (1)①sport.accdb ②号码牌 (2)①rs.Fields(“班级”) ②rs.MoveNext ③Search(x) ④key < a(m)
(共31张PPT)
第4节 查找算法
考试内容 考试要求
顺序查找算法思想及程序实现 c
对分查找算法思想及其变形的程序实现 c
一、顺序查找算法思想和程序实现
顺序查找的基本思想是从第一个数据开始，按顺序逐个将数据与给定的数据(查找键)进行比较，若某个数据和查找键相等，则查找成功，输出所查数据的位置；反之，输出未找到。
For i ＝ 1 To n
If a(i)＝key Then
Exit For
End If
Next i 代码分析：将数组中的每个元素逐个与key进行比较，如果相等则查找成功，循环结束。如果循环结束后，变量i的值等于n＋1，则意味着没有找到。顺序查找数组可以无序
二、对分查找算法思想
对分查找又称二分查找，是一种高效的查找方法。对分查找的前提是被查找的数据是有序的(升序或降序)。对分查找的基本思想是在有序的数列中，首先将要查找的数据与有序数列内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则就根据数据的有序性，再确定该数据的范围应该在数列的前半部分还是后半部分；在新确定的缩小范围内，继续按上述方法进行查找，直到找到要查找的数据，即查找成功，如果要查找的数据不存在，即查找不成功。
若key为查找关键字，数组d存放n个已按升序排序的数据。使用对分查找时，把查找范围[i，j]的中间位置上的数据d(m)与key进行比较，结果必然是如下三种情况之一：
(1)若key(2)key＝d(m)，找到了需要的数据；
(3)key>d(m)，查找键大于中点d(m)处的数据。由数组d中的数据的递减性，可以确定：在(i, m)内不可能存在值为key的数据，必须在新的范围(m＋1，j)中继续查找。
这样，除了出现情况(2)，在通过一次比较后，新的查找范围将不超过上次查找范围的一半。
数组d为例，观察对分查找的过程。要查找的数据key＝52，查找过程如下：
三、对分查找算法代码实现
i ＝ 1: j ＝ n: s ＝ 0
Do While i <＝ j
m ＝ (i ＋ j) \ 2
If a(m) ＝ key Then
s ＝ m: Exit Do
ElseIf key < a(m) Then
j ＝ m － 1
Else
i ＝ m ＋ 1
End If
Loop 左边程序实现在升序数组a(1)…a(n)中查找值等于key的元素，将其下标存储在s中。如果没有找到则s值为0，如果找到，则s存储对应元素的下标。
对分查找前提是数据有序，对n个数据查找，最多查找次数为Log2n＋1(向下取整)。
例如在有序数组a(1)…a(10000)中查找某个值，最多需要查找Log210000＋1，即14次
一、顺序查找算法思想和代码实现
【典例1】 小王拿着一大串钥匙去开仓库的某一扇门，由于钥匙上没有任何标记，小王只能将这一串钥匙一把一把地去试，从算法角度看，小王的做法属于( )
A.冒泡排序 B.选择排序
C.对分查找 D.顺序查找
解析 本题考查两个算法的区别。顺序查找的思想第从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较，若某个数据与给定的值相等，则查找成功，否则查找不成功。
答案 D
【变式训练】 用对分查找法和顺序查找法在数字序列“1，2，3，5，8，13，21，34，55”中查找数字13，两种方法都能访问到的数字是( )
A.3 B.5
C.8 D.34
解析 对分查找访问到的数字为8、21、13，顺序查找访问到的数字为1，2，3，5，8，13。两者共同为8。
答案 C
二、对分查找算法思想
【典例2】 已知单调函数f(x)在[0，1]区间存在一个x0，使f(x0)＝0。现用对分查找法搜索x0的值，开始搜索区间为[0，1]，若经过10次对分查找后还需继续搜索，则第11次搜索区间的长度为( )
A.1/2 B.1/10
C.1/102 D.1/210
解析 对分查找的每次区间变为上次的二分之一。第2次为原搜索区间的长度1/2，第3次为原搜索区间的长度1/4……第11次为原搜索区间的长度1/210，所以答案D。
答案 D
【变式训练】 下列有关查找的说法，正确的是( )
A.进行对分查找时，被查找的数据必须已按升序排列
B.进行对分查找时，如果查找的数据不存在，则无需输出结果
C.在新华字典中查找某个汉字，最适合使用顺序查找
答案 D
【典例3】 数组变量d(1)到d(8)的值依次为97、86、79、68、56、41、33、13，用“对分查找”找到“13”的过程中，依次被访问到的数据是( )
A.68、13 B.68、41、13
C.56、41、33、13 D.68、41、33、13
解析 本题考查标准的对分查找，查找中间项为m＝(i＋j)\2，经过4次对分查找。
答案 D
i 1 5 7 8
j 8 8 8 8
m 4 6 7 8
d(m) 68 41 33 13
【变式训练】 在有序单词序列“bike，cake，data，easy，feel，great，hive，mark，sweet”中，用对分查找算法找到“easy”过程中，依次被访问到的数据为( )
A.feel, data, easy B.great, data, easy
C.bike, cake, dada，easy D.feel，cake，data，easy
解析 本题考查标准的对分查找，查找中间项为m＝(i＋j)\2，经过4次对分查找。
i 1 1 3 4
j 9 4 4 4
m 5 2 3 4
d(m) feel cake data Easy
答案 D
三、对分查找算法代码实现
【典例4】 某对分査找算法的VB程序段如下：
i ＝ 1: j ＝ 9: n ＝ 0
key ＝ Val(Text1.Text)
Do While i <＝ j
n ＝ n ＋ 1
m ＝ Fix((i ＋ j) / 2)
If key ＝ d(m) Then Exit Do ′Exit Do表示退出循环
If key < d(m) Then j ＝ m － 1 Else i ＝ m ＋ 1
Loop
数组元素d(1)到d(9)的值依次为“7，12，18，25，39，58，61，72，86”。若该程序段运行结束后，n的值为2，则key的值是( )
A.39 B.18或61
C.18或72 D.12或61
解析 n代表查找次数，代入选项计算查找次数为2，即为答案。key＝12，第1次：m＝5，i＝1，j＝4；第2次：m＝2 ，d(m)＝12查找成功。key＝61，第1次：m＝5，i＝6，j＝9；第2次：m＝7 ，d(m)＝61查找成功。所以答案选D。
答案 D
【变式训练】 采用如下对分查找算法对数组a中7个有序数据“15，38，51，66，77，81，99”进行查找，查找数据为“55”，
i ＝ 1: j ＝ 7: x ＝ 55
Do While i <＝ j
m ＝ (i ＋ j) \ 2
If a(m) ＝ x Then Exit Do
If a(m) > x Then j ＝ m － 1 Else i ＝ m ＋ 1
Loop
执行完上述代码后，根据最终变量值判断下列表达式，其中正确的是( )
A.i＝m＋1 B.i＝m－1
C.j>m＋1 D.j解析 本题考查标准的对分查找，查找中间项为m＝(i＋j)\2，最终没有找到该数据。算法结束时i＝4，j＝3，m＝3，所以答案选A。
答案 A
i 1 1 3 4
j 7 3 3 3
m 4 2 3 ?
d(m) 66 38 51 ?
【典例5】 有如下VB程序段：
i ＝ 1 : j ＝ 10 : flag ＝ True : n ＝ 0
Key ＝ Val(Text1.Text)
Do While i <＝ j And flag ＝ True
m ＝ (i ＋ j) \ 2
If a(m) ＝ Key Then
flag ＝ False
ElseIf a(m) > Key Then
i ＝ m ＋ 1 : n ＝ n － 1
Else
j ＝ m － 1 : n ＝ n ＋ 1
End If
Loop
数组元素a(1)到a(10)依次是99, 94, 90, 87, 70，69，60，56，45，36，变量n的值最终是0，则文本框Text1输入的数字可能是( )
A.100 B.87 C.69 D.41
解析 本题考查的是对分查找的变形。当key＝100时，程序执行过程中，各个变量的值变化情况如下表所示：
i 1 1 1 1
j 10 4 1 0
m 5 2 1 ?
d(m) 70 94 99 ?
n 1 2 3 ?
当key＝87时，程序执行过程中，各个变量的值变化情况如下表所示：
i 1 1 3 4
j 10 4 4 4
m 5 2 3 4
d(m) 70 94 90 87
n 1 0 －1 ?
当key＝69时，程序执行过程中，各个变量的值变化情况如下表所示：
i 1 6 6
j 10 10 7
m 5 8 6
d(m) 70 56 69
n －1 0 ?
当key＝41时，程序执行过程中，各个变量的值变化情况如表所示。
i 1 6 9 10 10
j 10 10 10 10 9
m 5 8 9 10 ?
d(m) 70 56 45 36 ?
n －1 －2 －3 －2 ?
答案 C
【变式训练】 有如下VB程序段：
i ＝ 1: j ＝ 9: f ＝ False
Do While i <＝ j And Not f
m ＝ Fix((i ＋ j) / 2)
If a(m) ＝ Key Then
p ＝ m : f ＝ True
End If
If a(m) > Key Then
j ＝ m － 1
Else
i ＝ m ＋ 1
End If
Loop
If f ＝ True Then
Text1.Text＝“数据位置：” ＋ Str(p)
Else
Text1.Text＝“没有找到该数据！”
End If
数组元素a(1)到a(9)的值依次为10，15，30，32，38，42，45，48，68，若通过如下程序段查找数据key＝43，则在执行该程序段的过程中，依次访问的数据是( )
A.38，45，42 B. 38，45，48 C.38，48，42 D. 38，48，45
解析 本题考查的是对分查找的变形。在程序执行过程中，各个变量的值变化情况如下表所示，所以答案选A。
答案 A
i 1 6 6
j 9 9 6
m 5 7 6
d(m) 38 45 42
【典例6】 小明为了研究对分查找的过程中数据被访问的情况，编写了一个VB程序，功能如下：在列表框List1中显示已经排序的数据(存储在数组a中)，在文本框Text1中输入要查找的数据，单击“查找”按钮Command1后，在标签Label1中显示查找中依次被访问到的数据。程序运行界面如图所示。
实现上述功能的VB程序如下，但加框处代码有错，请改正。
Const n ＝ 10
Dim a(1 To n) As Integer
Dim s As String
Private Sub Form_Load()
′产生随机数依次存储在数组a中，代码略
′对数组a升序排序并在列表框输出，代码略
End Sub
Private Sub Command1_Click()
Dim x As Integer, p As Integer
x ＝ Val(Text1.Text)
s ＝ “ ”
If p > 0 Then s ＝ s ＋ “查找成功” Else s ＝ s ＋ “查找失败”
Label1.Caption ＝ “依次被访问的数据为：” ＋ s
End Sub
Function search(key As Integer) As Integer
Dim i As Integer, j As Integer, flag As Boolean
flag ＝ False
i ＝ 1: j ＝ n: search ＝ 0
Do While i <＝ j And Not flag
m ＝ (i ＋ j) \ 2
If a(m) ＝ key Then
search ＝ m
flag ＝ True
j ＝ m － 1
Else
i ＝ m ＋ 1
End If
s ＝ s ＋ Str(a(m)) ＋ “→”
Loop
End Function
程序中加框(1)处应改正为_________________________________________；
加框(2)处应改正为________________________________________________。
解析 (1)联系下文代码If p > 0 Then，需要对变量p赋值，结合函数search的功能：如果在数组a中找到要查找的数，函数search 返回该数在数组中的位置，如果没有找到，函数search 返回值为0，结合程序得知第1空为：p＝search(x)。
(2)在一个块If语句中结合对分查找算法得出第2空为： ElseIf Key < a(m) Then。
答案 (1)p＝search(x) (2)ElseIf Key < a(m) Then
