1、 1 高三算法复习十四(查找) 对分查找对分查找算法的基本思想算法的基本思想 对分查找的前提是数据已经【1】 。把要查找的数与数组 【2】 位 置的数进行比较，如果相等，则已找到并退出查找，否则将查找范围【3】 。 在确定了新的查找范围后，重复进行以上比较，直到找到或查找范围已经上界【4】 下界。 给出一组数据，要掌握利用对分查找方法找某个数依次查找到的数据及需要查找的 次数。若给出的数据无序，则必须先排序再查找。 对分查找算法的程序实现对分查找算法的程序实现 要求：设被查找的数据在数组 d 中，所有 n 个数据已按增序（从小到大）排列。要 查找的数在变量 key 中。若找到，输出该数据所在的
2、位置 pos=m；若未找到，pos 为 0， 输出结果找不到。 用变量 i、 j、 m 分别表示查找数据范围的底部 （数组的下界） 、 顶部 （数 组上界）和中间。 用循环语句可以实现不断查找，但由于查找的次数不能确定，因此不适合用 for 语 句，可以用【5】 语句。对分查找强调查找范围，变量 i、j 分别表示查找数据 范围的下界和上界，一旦当 iji，则表示查找范围已经不存在了，因此继续查找的条件 是【6】 。对分查找的基本操作是：计算中点位置 m比较【7】 ，并 做相应处理。此时可以用以下算法表示： 计算中点位置：m=【8】 比较 key 与 d(m)有三种情况： key=d(m)，表示
3、找到，记下中点位置 m，并结束查找(加上强制退出循环语句 exit do) keyd(m)，要找的数比中间位置的数大，则要到大的那部分去找，此时 j 不变，i=【10】 三种情况可以用多条件分支结构语句来实现， 并用变量 nc 表示查找的次数， 此时算 法得到进一步求精，对分查找的程序段如下： key=val(text1.text) nc=0:pos=0 i=1:j=n Do while i=j nc=nc+1 m=fix(i+j)/2) If key=d(m) then i=1:j=n Do while i=j 计算中点位置 m 比较 key 与 d(m)，并做相应处理 loop 2 pos
4、=m :exit do Elseif 【11】 Then j = m - 1 Else i = m + 1 End If Loop 【自我校对】 【1】有序 【2】中间 【3】缩小一半 【4】小于 【5】do while 【6】i=j 【7】key 与 d(m) 【8】fix(i+j)/2)或 Int(i+j)/2) 或 m=(i+j)2 均可 【9】m-1 【10】m+1 【11】keyd(m) 1、某公司委托花店公司给本公司职工生日的时候送花，花店设计了一个生日查询系统。 输入某个日期，就能查出所有这天生日的职工名单，并统计出生日人数。所有职工的姓 名和出生年月（以年月日形式，如 1982
5、1103）事先存放数组 na 和数组 birth 中。 界面如图 VB-1 所示，在文本框 text1 中输入查询的日期（以月日形式，如 0517） ，单击 “查询”按钮，在列表框 list1 中显示所有这个日子生日的职工名单，并在 label3 处显 示这天共有几个职工生日，如果人数为 0，就在列表框 list1 中显示“本天没有职工生 日” 。 Dim na (1 to n) as string,birth(1 to n) as string Private Sub Command1_Click() Dim x As String, t As String, i As Integer, c
6、 As Integer List1.Clear x = text1.text x存放需查询的日期 c = 0 c 保存这天生日的职工总人数 For i = 1 To n n 存放所有职工记录总数 t= mid(birth(i),5,4) t 存放职工的生日，即出生年月的后四位 If _(1)_ Then 判断职工的生日与输入的查询日期是否一致 c = c + 1 List1.AddItem na(i) End If Next i _(2)_ = “这天共有“ + Str(c) + “个职工生日“ If c=0 Then List1.AddItem “本天没有职工生日“ End Sub 程序中(
7、1)划线处应填入_ 程序中(2)划线处应填入_ 3 图 VB-1 2、某市近期向市民投放带 2B 开头尾数为 001 至 999 的机动车牌号，经过竞投有 200 个 牌号被首批车主投中。 下面 Visual Basic 程序段的功能是根据车牌号查找相应的车主身 份证号码， 其中车牌号按尾数从小到大的顺序存储在cno数组中， 身份证号码存储在cnum 数组中。 界面如图VB-1所示，在文本框Text1中输入一个车牌号，单击“开始查找“按钮后，在 文本框Text2中输出结果。如果查找成功，则输出对应的车主身份证号码，否则输出“找不 到“。 解决查找问题的算法流程图如图VB-2所示，相应的Visu
8、al Basic程序段如下，在和划 线处，填入合适的语句或表达式，把程序段补充完整。 Private Sub Command1_Click() Dim key As String , i As Integer Dim j As Integer , found As Boolean i = 1: j = 200 : found = False Do While i = j And Not found m = Int(i + j) / 2) If cno(m) = key Then found = True Else If Then i=m+1 Else j=m-1 End If Loop If
9、Not found Then Text2.Text = “找不到 “ Else Text2.Text = cnum(m) End Sub 程序中划线处应填入 程序中划线处应填入 3、超市进货时会将每个商品的条形码和价格输入计算机，并对所有商品按照条形码排序 4 （从小到大） ，顾客付款时只要把条形码输入电脑，电脑即可根据条形码找到该商品并显 示对应的价格。下列程序的功能是根据条形码查找对应商品的价格，所有商品的条形码和 价格分别保存在数组a和b中（并且已经按照条形码从小到大排序） ，第i个商品的条形码保 存在a(i)中，对应的价格保存在b(i)中，变量f是标志变量，如果值为True则说明找到了
10、 商品，若为False则说明没有找到。 程序界面如图VB-1所示，在文本框Text1中输入商品的条形码，单击“开始查找“按钮 （Command1）后，对应商品的价格在标签Label4中显示出来，如果未找到则显示“找不到 该商品，请重新输入条形码“。 解决此问题的算法流程图如图VB-2所示，相应的程序如下，在程序(1)和(2)划线处填 入适当的语句或表达式，将程序补充完整。 Private Sub Command1_Click() Dim x As String, i As Integer, j As Integer, m As Integer Dim f As Boolean x = Text1.Text i = 1: j = n: f = False n保存总的商品数 Do While (i = j) And Not (f) m = Fix(i + j) / 2) If _(1) _ Then f = True ElseIf x a(m) Then _(2)_ Else i = m + 1 End If Loop If f Then Label4.Caption = b(m) Else Label4.Caption = “找不到该商品，请重新输入条形码“ End If End Sub 程序中(1)划线处应填入_ 程序中(2)划线处应填入_ 图VB1
