第25课 对分查找复习课件-浙江省2022届高三选考信息技术一轮复习（19张PPT）

(共18张PPT)
Searching for points in VB selective review
25
VB选考复习之对分查找
00|回顾——对分查找的算法思想
对分查找
首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，则根据有序性，确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。
特点
①要求被查找数据必须有序。
②查找效率非常高，适用于大数据查找。
00|回顾——对分查找的算法思想
对分查找·演算一
用数组d(1 to 10)存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=48？
10
15
17
18
22
27
35
45
48
52
d(1)
d(2)
d(3)
d(4)
d(5)
d(6)
d(7)
d(8)
d(9)
d(10)
←i
←j
←mid
第1次查找：
范围为__________，i=________，j=_____，mid=___________。d(mid)=__________。
d(mid)_____key？
∴后续查找的范围应该是_______________。
d(1)~d(10)
1
10
(1+10)\2=5
d(5)=22
<
d(6)~d(10)
00|回顾——对分查找的算法思想
对分查找·演算一
用数组d(1 to 10)存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=48？
10
15
17
18
22
27
35
45
48
52
d(1)
d(2)
d(3)
d(4)
d(5)
d(6)
d(7)
d(8)
d(9)
d(10)
←i
←j
←mid
27
35
45
48
52
d(6)
d(7)
d(8)
d(9)
d(10)
←i
←j
←mid
第2次查找：范围为_____________，i=________，j=_____，mid=___________。d(mid)=______。
d(mid)_____key？
∴后续查找的范围应该是_______________。
d(6)~d(10)
6
10
(6+10)\2=8
45
<
d(9)~d(10)
00|回顾——对分查找的算法思想
用数组d(1 to 10)存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=48？
10
15
17
18
22
27
35
45
48
52
d(1)
d(2)
d(3)
d(4)
d(5)
d(6)
d(7)
d(8)
d(9)
d(10)
←i
←j
←mid
27
35
45
48
52
d(6)
d(7)
d(8)
d(9)
d(10)
←i
←j
←mid
48
52
d(9)
d(10)
←i
←j
←mid
第3次查找：范围为_____________，i=________，j=_____，mid=___________。d(mid)=______。
d(mid)_____key？
d(9)~d(10)
9
10
(9+10)\2=9
48
=
提示查找成功
对分查找·演算一
00|回顾——对分查找的算法思想
对分查找·演算二
用数组d(1 to 10)存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=17？
10
15
17
18
22
27
35
45
48
52
d(1)
d(2)
d(3)
d(4)
d(5)
d(6)
d(7)
d(8)
d(9)
d(10)
第一次查找：d(1)~d(10)，i=1，j=10，mid=5，d(mid)>key
第二次查找：d(1)~d(4)，i=1，j=4，mid=2，d(mid)第三次查找：d(3)~d(4)，i=3，j=4，mid=3，d(mid)=key
思考
①若d(mid)>key，则新查找的范围为______部分（前半/后半）
②若d(mid)>key ,i和j是如何变化的？
前半
i不变，j=mid-1
00|回顾——对分查找的算法思想
对分查找·演算三
用数组d(1 to 10)存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=20？
10
15
17
18
22
27
35
45
48
52
d(1)
d(2)
d(3)
d(4)
d(5)
d(6)
d(7)
d(8)
d(9)
d(10)
←i
←j
←mid
10
15
17
18
d(1)
d(2)
d(3)
d(4)
←i
←j
←mid
17
18
d(3)
d(4)
←i
←j
←mid
18
d(4)
←i,j,mid
思考
继续进行查找的条件是什么？在什么情况下查找会结束？
当i<=j时，重复查找，无论找到找不到，查找都会结束。
00|回顾——对分查找的算法思想
对分查找·归纳
（1）key与d(mid)的大小比较影响i，j在后续查找中的取值。
①若d(mid)②若d(mid)>key，则j=mid-1，i不变
（2）继续重复进行查找的条件。
当i<=j时
（3）对分查找最多的查找次数(n个数据)。
最多次数=Int(log2n)+1
∵n个数据对分x次最后变为1个数据
∴n*(1/2)^x=1
∴x=log2n
∵最后一个数据还要参与一次查找
∴最多次数=Int(log2n)+1
00|回顾——对分查找的典型程序段
现有n个从小到大的数据，存放在数组a(1 To n)中，要查找的数key。
i=1:j=n
x=0
Do While__________
m=______________
If d(m)=key Then
x=m
Exit Do
End If
If d(m)>key Then
_________
Else
_________
End If
Loop
If x<>0 Then
list1.additem “查找成功下标为”+str(x)
Else
list1.additem “查找失败”
End If
i<=j
(i+j)\2
j=m-1
i=m+1
①给i,j赋初值，用x来记录查找元素下标
②当i<=j时，重复执行查找工作
③对分，取中值m
④判断中值是否就是查找键
⑤如果中值不是查找键，则判定下一个查找范围应该在前半部分还是在后半部分。注意i和j的控制。
⑥输出查找结果
00|回顾——对分查找的典型代码段
其中取中间位置 m 的方法常见的还有：
m=(i+j)\2
m=Int((i+j)/2)
m=Int((i+j+1)/2)
m=Fix((i+j)/2)
m =Fix((i + j) / 2 + 0.5)
01|第24课 作业讲解
1. 数组元素d(1)到d(6)的值依次为“11,19,25,31,47,58”。Key=31，i的初始值是1，j的初始值是的6，进行对分查找，找到即停止查找，停止时下列选项中正确的是( )
A. 变量i的值为3
B.变量i的值为4
C.变量j的值为6
D. 变量j的值为5
d（1） d（2） d（3） d（4） d（5） d（6）
11 19 25 31 47 58
B
01|第24课 作业讲解
2．在已排序的数组d(数组元素d(1)≥d(2)≥…≥d(n))中查找键值为key的数，其对分查找的VB程序段如下：
i=1：j= n
xb= 0
Do While i <= j
m=Fix((i+j)/2)
If d(m) = Key Then xb = m :Exit Do
If Then j =m – 1 Else i=m+1
Loop
划线处的语句为( )
A. key>d(m) B. keyd(m) D. key=d(m)
A
01|第24课 作业讲解
3.某对分査找算法的 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
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
C
01|第24课 作业讲解
4. 某对分查找算法的VB程序段如下：
c= 0：i =1: j =8: f = False
key = Val(Text1.Text)
Do While i < = j And Not f
m =Int((i + j) / 2 + 0.5)
c= c+ 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(8)的值依次为“97, 79, 68,48, 35,23,18,10”，若运行该程序段后，c的值为2，则Text1中输入的值是( )
A.68或18 B.68或23 C.79或23 D.79或18
A
01|第24课 作业讲解
5．某对分查找算法如下:
Key=val(text1.text)
Text2.text=””
Flag=True
i=1:j=8
do while i<=j and flag
m=(i+j)\2
if key=a(m) then
flag=false
elseif key>a(m) then
i=m+1
else
j=m-1
end if
text2.text=text2.text+str(m)
loop
数组a(1)到a(8)的值依次为”1, 3 ,5, 8 ,10 ,13 ,16,21”，在text1中输入7， 执行该程序段，下列说法正确的是（ ）
A、flag值为false B、文本框text2中显示内容为“ 4 2 3” C、i值为3 D、j值为4
B
01|第24课 作业讲解
6. 某对分查找算法的 VB 程序段如下：
t = "":i = 0 : j = 9 : key=62: f = False
Do While i <= j And Not f
m = Fix((i + j) / 2)
t = t + Str(m)
If a(m) = key Then
f = True
ElseIf a(m) > key Then
i = m + 1
t = t + "→"
Else
j = m - 1
t = t + "←"
End If
Loop
数组元素 a(0)到 a(9)的值依次为“99，94，90，87，78，70，63，56，45，36”，执行该程序段，t的值是（ ）
"4→ 7← 5→" B. "4→ 7← 5→ 6"
C."4→ 7← 5→ 6→“ D. "4→ 7← 5"
C
01|第24课 作业讲解
7．有如下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
C
02|对分查找训练
课堂练习1：
使用对分查找算法查找数据9，访问到的数据依次是____________________。
VB语句如下，请填空：
Key = Val(Text1.Text)
i = 1
j = n
Do While i <= j
_________________
If____________ Then
Text1.text = "在数组的 " + Str(M) + " 位置中"
Exit Sub
End If
If Key > d(m) Then
__________
Else
___________
End If
Loop
if i>j then Label6.Caption = "在数组中没有找到"
13,5,9
m=(i+j)\2
d(m)=key
i=m+1
j=m-1