《对分查找算法》一轮复习.pptx

德清一中 杨月霞
《对分查找算法》复习
前提：前提是被查找的数据必须是 的（递增/递减）
意义：对分查找的高效性。
试想：将全国13亿人按身份证号排列后，你可在31次比较
后找到这个人的信息。
若用顺序查找还有这个效率吗？
有序
Key = Val()
i = 1:j = n：p=0
Do While i <= j
m=(i+j)\2
If a(m) = Key Then
p=m:Exit Do
Else If a(m) < Key Then
Else

End If
Loop
对分查找的核心代码：（以n个元素的递增数组为例）
i=m+1
j=m-1
Dim a(1 to n) as integer,当n=10时数组元素排列如下：
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)
1
3
4
7
11
16
19
20
27
30
第一次
a(1)
1
a(2)
3
a(3)
4
a(4)
7
a(5)
11
a(6)
16
a(7)
19
a(8)
20
a(9)
27
a(10)
30
第二次
a(1)
1
a(2)
3
a(3)
4
a(4)
7
a(5)
11
m=5
a(6)
16
a(7)
19
a(8)
20
a(9)
27
a(10)
30
第三次
a(1)
1
a(2)
3
a(3)
4
a(4)
7
a(5)
11
m=5
a(6)
16
i=6
a(7)
19
a(8)
20
a(9)
27
a(10)
30
第四次
非法区间
a(2)
3
a(3)
4
a(4)
7
a(5)
11
m=5
a(6)
16
i=6
a(7)
19
a(8)
20
a(9)
27
i=9
m=9
a(10)
30
key=26
i=1
j=10
m=5
i=6
j=10
m=8
i=9
m=9
j=10
j=8
对分查找一般过程归纳（以n个元素的递增数组为例）：
1、i的初值=1； j的初值=n
2、中间数的下标m与i，j的关系是：m=Int((i+j)/2)
3、确定退出循环的条件
①区间的二个端点 i,j必须满足的条件是i<=j
②标志变量取反值flag=true
4、若key>d(m)，说明应在下半区继续查找，修改i 还
是j? i=m+1
若key<d(m)，说明应在上半区继续查找，修改i 还
是j? j=m-1
1. (必做）数组变量d（1）到d（8）的值依次为87、76、69、66、56、45、37、23，用“对分查找”找到“69”的过程中，依次被访问到的数据是（）
A．69
B．66、69
C．66、76、69
D．56、66、76、69
热身训练
2.（选做）在有序单词序列"bike,cake,data,easy,feel, great,hive,mark, sweet"中,用对分查找算法找到" easy"过程中,依次被访问到的数据为
feel, data. easy
great, data, easy
bike, cake, data, easy
feel. cake. data, easy
对分查找考点分析：
1. 某对分査找算法的VB程序段如下:
i = 1: j = 9: n = 0
key = Val()
Do While i <= j
n = n + 1
m = Fix((i + j) / 2)
If key = d(m) Then 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的值是
B. 12或61 D. 7或58
（一）常规考点
写出每一次循环结束后m,i,