13-VB程序设计--对分查找算法1(13)

一、顺序查找算法回顾

1、顺序查找思路：

1) 将被查的数存放到数组中（比如数组d ），待查的数据存放在某变量中（比如变量key ）2) 从数组第1个元素开始，逐个与要查找的数比较

2、顺序查找过程 1）将被查的10个数存放到数组d ，将待查的数据存放到变量key 2）从数组第1个元素开始，逐个与变量key 比较，对于某个数组元素

若d(i)=key

，表示查找成功，输出该数组元素的下标 i ，并停止比较 若d(i)<>key ，则数组的下一个元素d(i+1)继续与key 比较...... 3）若找遍了所有元素，没有一个元素d(i)=key ，表示3、顺序查找方法归纳：笨拙4、上次课堂结尾的几个话题

话题1：如何查英文词典（不可能采用顺序查找的！）

话题2：如何在最短时间猜中1000元以内商品的价格？（每次猜中间价格！）

话题3：如何在10个有序的数“98、88、82、78、70、67、65、56、49、28”中查找 49 这个数 如何在10个有序的数“28、49、56、65、67、70、78、82、88、98”中查找 99 这个数

有序数据采用“对分查找”方法（取中间的数进行比较）

核心要点：区间（i,j)的中间数编号m=Int((i+j)/2)

二、对分查找：前提是被查找的数据必须是有序的（递增/递减）

1、对分查找的基本思想：每次将查找内容与有序数组内中间的那个数进行比较！

第二章：算法实例—对分查找算法1(13)

算法与程序设计

1) 将被查找的数存放到数组中(必须有序！)，待查数据存放在某变量中（比如变量key）

2) 区间（i,j）的起始为（1，n)，即初始值：i=1，j=n，(注意i<=j)

3）每次将查找内容与有序数组内中间那个数比较。区间（i,j)的中间数编号m=Int((i+j)/2)如果二者相等，则查找成功

若二者不同，则根据数组的有序性可以确定在数组的前半部分还是后半部分继续进行查找。

4）直到找到，或者无法组成新的查找区间（即找不到）为止！

2、对分查找过程示例1：在递增的数组d中寻找key=35这个数

第3次

末数

3、对分查找过程示例2：在递减的数组d中寻找key=66这个数

第3次第1次第2次

第1次第2次第3次

末数

三、对分查找算法的程序实现！

1、算法要点（从前面的练习中去感觉！）

1、初值i=1,j=n

2、循环条件：i<=j

3、根据i,j计算m=Int((i+j)/2) 或者 m=Fix((i+j)/2)

4、比较key与d(m)

若key=d(m)查找成功，输出m

若key

若key>d(m)，则在下半区继续查找（增序为例），只要修改i=m+1即可思考：对分查找该用什么类型的循环呢？

2、对分查找的程序理解!

假设有10个数据已经按照升序存放在数组 D中，要查找的数据通过文本框Text1输入Dim d( 1 to 10) As Integer

key=Val(Text1.Text)

i=1 : j=10 '查找区间初始化

xb=0 '记忆查找成功时的下标

nc=0 '统计查找次数

Do While i<=j '为何不用For循环？

nc=nc+1 'nc记录查找次数

m=Fix((i+j)/2) '计算出中间位置，或m=Int((i+j)/2)

If d(m)=key Then '查找成功立即终止循环

xb=m'查找成功时变量xb记忆住数组下标

Exit Do

End If

If key

j=m-1

Else'准备在下半区继续查找

i=m+1

End If

Loop

If xb<>0 Then '查找成功，输出下标xb

Print xb

Else '查找不成功

Print "没有找到"

End If

3、对分查找的程序流程图（略）

四、对分查找算法巩固练习

1、启动D：\下的“课堂练习.exe”，完成第27套课堂练习

2、做完后将"批改27.批改"上传到班级FTP自己的文件夹内（ftp://10.7.3.100）

中（比如变量key）

不到的结论。

key=49key=99

输出下标 5

输出 0 8”中查找49这个数98”中查找 99这个数

13)注意：ftp地址已变更为：

ftp://10.7.3.100

（比如变量key）

数编号m=Int((i+j)/2)

分继续进行查找。

第4次

i,j,m=7

第4次

=m-1即可=m+1即可