5.4 对分查找程序实现 导学案 -2021-2022学年高中信息技术浙教版选修1
高二信息技术导学案 VB模块 班级 姓名
《对分查找程序实现》导学案
[考试要求]
1.对分查找算法思想 (c)
2.对分查找程序实现 (c)
[学习目标]
1. 对比顺序查找,掌握对分查找的算法思想。
2. 分解对分查找的算法思想,构建对分查找的代码
3. 充分解读和理解对分查找的程序代码
[自主学习]
一、 知识梳理
1、 思想:首先将查找的数与 (有序/无序)数组内处于 位置的数据比较,如果中间位置上的数与查找的数不同,则根据有序性,确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内,继续按上述方法,直到获得最终结果。
2、 特点:①要求被查找数据必须 。
②查找效率 ,适用于大数据查找。
二、自我检测
1.在一个有序数据序列中,采用对分查找算法查找,则下面说法正确的是( )
A.对分查找算法的数据,必须是降序数列
B.对分查找算法的数据,必须是升序数列
C.对分查找算法的查找速度一定比顺序查找算法快
D.对n个数采用对分查找算法的最多次数是log2n次
2.数组变量d(1)到d(8)的值依次为97、86、79、68、56、41、33、13,用“标准”对分查找算法查找“13”的过程中,依次被访问到的数据是( )
A.68、13 B.68、41、13 C.56、41、33、13 D.68、41、33、13
3.某电视台有一档与观众互动的猪物品价格的节目,让观众采用对分查找的算法在1- 1000元内进行竞猜,如某件物品价格为250元,则此价格被猜中至少需要的次数是( )
A.1 B.2 C.3 D.4
4.在有序数组内进行对分查找,如果中间位置上的元素内的数值大于查找键值,而接下来的查找范围确定在数组的后半部分测数组的排序方式为( )
A升序 B.降序 C.无序 D.无法确定
5.7位学生的身高(单位:cm)从高到低依次为:178,177,175,172,170,165,162。用对分查找法找到178所需要的查找次数是( )
A.1 B.2 C.3 D.4
6.对22个记录的有序表作对分查找,当查找失败时,至少需要比较多少次关键字( )
A.3 B.4 C.5 D.6
[课堂练习]
1.某数组的6个元素依次为“27,32,57,78,80,90”。若对该数组进行顺序查找,其平均查找次数为(1+2+3+4+5+6) /6=7/2:若对该数组进行对分查找,其平均查找次数为( )
A.7/2 B. 7/3 C.5/2 D. 2
2.在已排序的数组d(数组元素d(1)≥d(2)≥…≥d(n))中查找键值为key的数,其对分查找的VB程序段如下:
i=1:j= n
xb= O
Do Whilei <=j
m=Fix((i+j)/2)
If d(m) = Key Then
xb = m
Exit Do
高二信息技术导学案 VB模块 班级 姓名
End lf
If Tlren
j =m -1
Else
i=m+1
End if
Loop
划线处的语句为( )
A. key>d(m) B. key<d( m) C. key<>d(m) D. key=d(m)
3.有10个数据:83、80、66、46、44、36、21、16、15、12依次存放在数组元素a(1)到a(10)中,部分VB程序段如下所示:
key = Val(Text1.Text)
i = 1: j = 10: Text2.Text = ""
Do While i <= j
m = (i + j+ 1) \2
If key = a(m) Then Exit Do
If key >a(m) Then j = m-1 Else i = m+1
Text2.Text = Text2.Text + Str(a(m))
Loop
文本框Text1中输入80,执行该程序段,文本框Text2中显示的是( )
A. 36 66 B. 44 80 C. 36 46 D.44 66
4.某对分查找算法的VB程序段如下:
i=1:j=8:c=0
Do While i<=j
c=c+l
m= Fix((i+j)/2)
If key=b(m) Then Exit Do
If key<b(m) Then j=m-l Else i=m+l
Loop
数组元素b(l)到b(8)的值依次为“22,32,39,48,71,82,96,106”。若该程序段运行结束后,c的值为2,则key的值是( )
A.48或32 B.48或96 C.32或82 D.82或96
[课后练习]
1.己知一元二次函数f(x)=在区间[0,1]之间必定存在着一个极大点x0,使f(x0)达到最大值。现用对分查找算法搜索x0的值,开始搜索区间为[O,1],在搜索到第n次时找到x0,已知第n次搜索区间的长度是1/32,则n的值是( )
A.3 B.4 C.5 D.6
2.下列VB程序段功能为:在降序排序数组a中(a(1)≥a(2)≥…≥a(n))查找文本框Text1中输入的数据,若能找到,则输出该数在数组a中第一次出现的位置,否则输出“找不到”。
key= Val(Textl.Text)
i=1:j=n
Do While i <j
m=(i+j)\2
lf ① Then
i=m+1
Else
②
End lf