例题：对分查找
1、首先在通用声明事件里定义数组d变量为全局变量。 Dim d(1 To 10) As Integer
2、程序一运行，生成10个3位整数，显示在标签1中。 Private Sub Form_Load() Label1.Caption = "" Randomize For i = 1 To 10 d(i) = Int(Rnd * 101 + 100) Label1.Caption = Label1.Caption & d(i) & " " Next i End Sub
数组d( ): Key=52
下标
元素
1 2 3
10 15 17
4
我们用变量 I和J记录所 要查找范围的起始和终止 位置
18
22 27 35 45
5 6 7 8 9 10
48
52 65 67 72
i=9
第2次比较后： Key<d(m) 查找范围应该 变成d(9)~d(11)
11
12 13 14 15 16
对分查找程序的基本框架： Private Sub Command1_Click() i ＝ 1: j ＝ n Do While i <＝ j m ＝ (i ＋ j) \ 2 If d(m) ＝ Key Then '输出结果，退出查找(代码略) ElseIf Key < d(m) Then j＝m－1 Else i＝m＋1 End If Loop End Sub
设置第一数和第n数 求中间数
1．下列有关查找的说法，正确的是 A．顺序查找时，被查找的数据必须有序 B．对分查找时，被查找的数据不一定有序 C．顺序查找总能找到要查找的关键字 D．一般情况下，对分查找的效率较高
( D )
2．某网站报名参加免费三亚游的会员序列号有：101、135、 238、342、450、558、633、708、846、910。采用对分查 找，查找到序列号为846号网友信息的过程中，依次被查 找的序列号是 ( A ) A．450、708、846 B．450、708、910、846 C．558、708、846 D．558、708、910、846
12 13 14 15 16
3．对分查找算法的表示 使用对分查找在数组变量d中查找key，用自然语言描述的算 法如下： (1)(确定初始查找范围)i←1，j←n。 (2)(是否能继续查找？)如果i≤j，那么转到(4)。 (3)(找不到)输入出结果0，算法结束。 (4)(计算中点位置)m←(i＋j)\2。 (5)(相等？)如果d(m)＝key，那么转到(7)。 (6)(修改查找范围)如果key<d(m)，那么j←m－1；如果 key>d(m),那么i←m＋1，转到(2)。 (7)(找到)输出结果m，算法结束。
7．使用对分查找在已排序的数组d(数组元素d(l)≤d(2) ≤…≤d(n))中查找key的算法流程图如下。其中①、②框中的 内容分别是 ( C )
A．①j←m＋1 ②i←m＋1 B．①j←m—1 ②i←m－1 C．①j←m－1 ②i←m＋1 D．①j←m ＋ 1 ②i←m－1
8．有两组数据： ①54、31、43、12、8、73、56、34、89、60、23、67 ②87、83、75、70、63、59、55、37、33、21、17、7 下列有关查找方法描述不正确的是 ( C) A．①可以直接使用顺序查找 B．②可以直接使用对分查找 C．①可以直接使用对分查找 D．②可以直接使用顺序查找 9．某查找算法的部分VB程序代码如下： t ＝ False i＝0 Do While i < 7 And t ＝ False i＝i＋1 If d(i) ＝ Key Then t ＝ True Loop If t ＝ False Then i ＝ 0 数组元素d(1)到d(7)的数据依次为“8、9、5、8、4、7、 8”，当变量key的值为8时，运用该算法处理后，变量i的 值是 ( A ) A．1 B．2 C．4 D．7
m=fix((i+j)/2)
=12
85
97 9815 17
Key=52
3
4
5 6 7 8 9 10
18
22 27 35 45 48 52 65 67 72 85 97 98
第3次比较后： Key=d(m) 找到了 i=9 m=fix((i+j)/2) j=11 =10
11
这样，除了出现情况(2)，在通过一次比较后，新的查找范围 将不超过上次查找范围的一半。
下标
元素
1
10 15 17
i=1
（1）过程：
2 3 4 5 6 7 8
我们用变量 I和J记录所 要查找范围的起始和终止 位置
18
22 27 35 45 48 52 65 67
Key=52 数组d(i ):
9
10 11 12 13 14 15
4、在文本框1中输入要找的数，单击“对分查找”按钮，在文本框2中 显示找到的结果。 Private Sub Command2_Click() Dim key As Integer, m As Integer, i As Integer, j As Integer key = Val(Text1.Text) i = 1: j = 10 Do While i <= j m = (i + j) \ 2 If d(m) = key Then Text2.Text = "找到了，是第" & m & "个" Exit Sub End If If d(m) < key Then i=m+1 Else j=m-1 End If Loop Text2.Text = "找不到" End Sub
3．某电子图书馆网站有10万本图书记录(已索引排序)，假设 从中取出一条记录并与待查找项进行比较所花时间为10毫 秒，则用对分法在该系统中查找任意一本指定图书最多花 费的时间约为 ( D ) A．100万毫秒 B．50万毫秒 C．10毫秒 D．170毫秒 4．某数组有7个元素，依次为158、234、369、478、552、 697、748。若采用对分查找法在该数组中查找数据748， 需要查找的次数是 ( C ) A．1 B．2 C．3 D．4
相应的查找部分程序段如下：
Dim a(1 To n) As Long Dim b(1 To n) As Single Private Sub Command1_Click() Dim x As Long, i As Long, j As Long, m As Long, f As Boolean x ＝ Val(Text1.Text) i ＝ 1: j ＝ n: f ＝ False ' 设账号总数为n Do While (i <＝ j) And Not f ① If x ＝ a(m) Then f ＝ True ElseIf x < a(m) Then j＝m－1 Else ② End If Loop If f Then Label2.Caption ＝ “此账号余额为” ＋ Str(b(m)) ＋ “元” Else Label2.Caption ＝ “找不到此账号，请重新输入” End If End Sub Private Sub Form_Load() ' 此过程用于对数组a和数组b进行初始赋值，代码略 End Sub
m＝ (i＋j)\2 或m=fix((i+j)/2)
=8 =8
72
85 97 98
第1次比较后： Key>d(m) 查找范围应该 变成d(9)~d(16)
16
j=16
Int、Fix 函数:
返回数字的整数部分。
Int函数和 Fix 函数都删除 number 参数的小数部分并 返回以整数表示的结果。 Int 和 Fix 函数的区别在于如果 number 参数为负数时， Int 函数返回小于或等于 number 的第一个负整数，而 Fix 函数返回大于或等于 number 参数的第一个负整数。 例如，Int 将 -8.9 转换为 -9，而 Fix 函数将 -8.9 转换 为 -8。
3、单击“升序排序”按钮，按从小到大进行排序，并将结果 显示在标签2中。 Private Sub Command1_Click() For i = 1 To 9 Min = d(i) For j = i + 1 To 10 If d(j) < Min Then Min = d(j) t = d(i): d(i) = d(j): d(j) = t End If Next j Next i Label2.Caption = "" For i = 1 To 10 Label2.Caption = Label2.Caption & d(i) & " " Next i End Sub
5．在有序单词序列：As、Book、Door、English、Floyd、 Good、Hello、Sun中，用对分查找法找到单词“Good”所 需要的查找次数是 ) B ( A．1 B．2 C．3 D．4 6．某8位男生的肺活量数据放在数组元素a(l)到a(8)中，其数 据依次为“3205、3408、3471、3498、3621、3829、4233 、4540”。使用对分查找，设定查找键key，若第一个被访 问到的数据是3498，小于key值，则第二个被访问到的数据 是 ( B ) A．3408 B．3829 C．4233 D．4540
对分查找算法
及程序实现
1．对分查找的概念
对分查找又称二分查找，是一种高效的查找方法。对分 查找的前提是，被查找的数据序列是有序的(升序或降序)。 对分查找的基本思想是在有序的数列中，首先将要查找 的数据与有序数列内处于中间位置的数据进行比较，如果两 者相等，则查找成功；否则就根据数据的有序性，再确定该 数据的范围应该在数列的前半部分还是后半部分；在新确定 的缩少范围内，继续按上述方法进行查找，直到找到要查找 的数据，即查找成功，如果要查找的数据不存在，即查找不 成功。 注：变量定义描述：假设将查找的那个数定义为一个变量key, 数组d(有n个数据)的中间位置定义为变量m，变量i记录查找范 围内的第一个元素的下标，变量i的初值为1，变量j记录查找 范围内最后一个数组元素的下标，变量j的初值为n.