资源简介

(共23张PPT)
CHZX
5.5 对分查找
浙江省高中信息技术 选择性必修一 《数据与数据结构》
昌化中学 应彤鑫
考点剖析
题号 2016.4 2016.11 2017.4 2017.11 2018.4 2019.4 2020.1 2020.7 2020.7 2021.1 2021.6
1 信息的概念 会声会影 信息安全道德 信息的概念 信息的概念 信息的概念 信息处理描述 信息与信息处理 信息与信息处理 信息和信息技术基本概念 信息和信息处理基本概念
2 smtp协议 网页URL等 网页html等 浏览相关协议等 浏览相关协议等 电子邮局协议 人工智能 网页与浏览器 网页与浏览器 信息安全 网页与浏览器基本概念
3 OCR操作应用 人工智能、OCR Word批注修订 人工智能 OCR操作应用 人工智能 数据库相关知识 数据表数据类型 数据表数据类型 数据表名称、字段、数据类型 Access 数据库
（数表名称、数据类型、导出到Excel）
4 数据表操作知识 数据表（设计视图） 内码、进制转换 数据库相关知识 数据库相关知识 数据表相关知识 计算机信息编码 进制转换 进制转换 信息编码相关知识 进制转换与ASCII码
5 流程图执行结果 流程图执行结果 数据表操作的说法 流程图执行结果 字符内码 进制转换 PS基本操作 PS基本操作 Photoshop基本操作 GoldWave声音处理 Photoshop 图像处理
6 会声会影 进制转换 流程图执行结果 进制转换 GoldWave 流程图执行结果 视频数字化压缩比 声音容量计算 声音容量计算 图像容量计算、压缩比 图像存储容量计算
7 进制转换 GoldWav 作品规划制作脚本 GoldWav 流程图执行结果 GoldWave If语句变式 VB表达式 VB算术表达式 VB算术表达式 VB算术表达式
8 PS基本操作 PS基本操作 GoldWave PS基本操作 PS基本操作 PS基本操作 流程图执行结果 流程图执行结果 流程图执行结果 流程图执行结果 流程图执行结果
9 Flash基本操作 Flash_按钮 Flash_补间属性 Flash基本操作 Flash_按钮 Flash_按钮操作 冒泡排序交换次数 For循环程序执行结果(字符串) For循环程序执行结果(字符串) 枚举算法应用（选择填空） 枚举算法应用（选择填空）
10 图像数字化 图像数字化 视频数字化 图像容量比 视频数字化 图像数字化 For循环程序执行结果 Do循环程序选择填空 Do循环程序选择填空 字符串相关运用 对分查找算法变式
11 排序算法_For 对称字符串 For程序 对分查找 For程序结果 For程序结果 Do循环程序结果 程序功能代码排序 对分查找 对分查找 冒泡排序算法 字符串处理结果
12 对分查找 对分查找 选择排序改进 对分查找 对分查找 对分查找 对分查找 冒泡排序变式 冒泡排序变式 对分查找 冒泡排序算法及其变式
考点剖析
对分查找
通过实例分析，掌握对分查找的基本思想和程序实现。
借助对分查找的基本实现，实现对分查找变式的应用。
理解对分查找的应用场景，能在实际问题解决中运用对分查找。
目标分解
基础落实
算法思想
经典程序
01
基础落实
Jichu luoshi
算法思想
首先将查找数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找数不同，则根据有序性，确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。
①要求被查找数据必须有序。
②查找效率非常高，适用于大数据查找。
算法特点
算法设计
开始
i=0,j=9
d[m]=key
d[m]查找成功
查找失败
结束
Y
N
Y
N
Y
N
m=
i<=j
(i+j)//2
i=m+1
j=m-1
基础落实
Jichu luoshi
算法描述
key=int(input())
d=[10,15,17,18,22,27,35,45,48,52]
f=False
i=0
j=
while :
m=
if d[m]==key:
f=True
break
if d[m]>key:
else:
if f==True:
print("查找成功！下标为"+str(m))
else:
print("没有找到！")
i<=j
(i+j)//2
j=m-1
i=m+1
①给i,j赋初值：i查找的起点
j查找的终点
②当i<=j时，重复执行查找工作
③对分，当前查找的中间值m
④判断中值是否就是查找键
⑤如果中值不是查找键，则判定下一个查找范围应该在前半部分还是在后半部分。注意i和j的控制。
⑥输出查找结果
len(d)-1
基础落实
Jichu luoshi
代码变式一：中间值变化
key=int(input())
d=[10,15,17,18,22,27,35,45,48,52]
f=False
i=0
j=len(d)-1
while i<=j:
m=(i+j)//2
if d[m]==key:
f=True
break
if d[m]>key:
j=m-1
else:
i=m+1
if f==True:
print("查找成功！下标为"+str(m))
else:
print("没有找到！")
① m=int(（i+j）/2)
③ m=（i+j+1）//2
④ m=int(（i+j+1）/2)
⑤ m=round(（i+j）/2)
② m=int(（i+j）/2+0.5)
基础落实
Jichu luoshi
代码变式一：中间值变化
基础落实
Jichu luoshi
中间值 [0,8] [0,9]
m=(i+j)//2 4 4
m=int(（i+j）/2) 4 4
m=int(（i+j）/2+0.5) 4 5
m=（i+j+1）//2 4 5
m=int(（i+j+1）/2) 4 5
m=round(（i+j）/2) 4 5
代码变式二：增加一些变量
i=0
j=len(d)-1
while i<=j:
m=(i+j)//2
if d[m]==key:
break
if d[m]>key:
j=m-1
else:
i=m+1
c+=1 功能：用于统计查找次数
s=“L”或s=s+”L” 功能：用于记录变化过程
s=“R”或s=s+”R” 功能：用于记录变化过程
基础落实
Jichu luoshi
代码变式三：找到不结束
i=0
j=len(d)-1
while i<=j:
m=(i+j)//2
if d[m]==key:
break
if d[m]>key:
j=m-1
else:
i=m+1
if d[m]>key:
j=m-1
else:
i=m+1
if d[m]>=key:
j=m-1
else:
i=m+1
基础落实
Jichu luoshi
下标 0 1 2 3 4 5 6 7 8 9
值 8 17 24 30 36 40 55 58 61 66
① i m j
If d[m]==key:
f=True
if d[m]>key:
j=m-1
else:
i=m+1
运用激活
经典再现
考法分类
例题实践
02
运用激活
Yunyong jihuo
经典再现
【例1】某二分查找算法的Python程序段如下：
a = [8,17,24,30,36,40,55,58,61,66]
key = int(input())
i,j = 0,9
res = []
while i<=j:
m = (i+j+1)//2
if key == a[m]:
break
elif keyj=m-1
else:
i=m+1
res.append(a[m])
print(res)
执行该程序段，当输入的值为30时，程序输出结果为（ ）
A.[40,24] B.[40,24,36] C.[24,36] D.[36,17,24]
考点：查找路径
核心：快速定位中间值m
方法：表格法
B
下标 0 1 2 3 4 5 6 7 8 9
值 8 17 24 30 36 40 55 58 61 66
① i m j
② i m j
③ ijm
运用激活
Yunyong jihuo
变式训练
【变式训练1】有如下python程序段：
key=int(input("请输入待查数据值："))
d=[17,18,20,23,24,25,28,32,34,35]
s="";i=0;j=len(d)-1
while i<=j:
m=(i+j)//2
s=s+" "+str(d[m])
if key < d[m]:
j=m-1
else:
i=m+1
print(s)
输入待查数据值为 20，执行该程序段，则输出的结果是（ ）
A．24 18 20 23 B．24 18 20 C．25 20 D．25 20 23
A
运用激活
Yunyong jihuo
经典再现
【例2】某二分查找算法的程序如下：
i,j＝0,7
n＝0
while i<＝ j ：
n＝n＋1
m＝(i ＋ j)//2
if key＝＝d[m]：
break
elif key > d[m]：
j＝m－1
else：
i＝m＋1
数组元素d[0]到d[7]的值依次为″83，75，62，41，33，27，16，2″，若运行该程序段后，n的值为2，则key的值可能是(　　)
A.62或16 B.62或27 C.75或27 D.75或16
C
考点：查找次数
核心：快速定位中间值m
方法：二叉树法
41
75
27
运用激活
Yunyong jihuo
变式训练
【变式训练2】某二分查找算法的程序如下：
i=0
j=9
c=0
while i<=j:
c+=1
m=(i+j)//2
if a[m]i=m+1
else:
j=m-1
print(c)
数组元素a的值依次为″2,13,13,14,23,26,29,31,32,38 ″，若运行该程序段后，c的值为3，则key的值不可能的是(　　)
A.11 B.13 C.29 D.32
C
运用激活
Yunyong jihuo
经典再现
【例3】有如下python程序段：
a=[11，22，33，44，55，66]
i=0:j=5:p=0
key=23
while i<=j:
p+=1
m=(i+j)//2
if a[m]==key:
break
if a[m]>key:
j=m-1
else:
i=m+1
对数组 a 中 6 个有序数据“11，22，33，44，55，66”，用上述程序代码查找数据 “23”，程序执行完毕后，下列各变量值正确的是( )
A．i=2 B．j=2 C．m=2 D．p=2
A
考点：变量的值
核心：模拟查找过程
方法：表格法
运用激活
Yunyong jihuo
变式训练
【变式训练3】某算法的 VB 程序段如下:
key=randint(0,3)*2+13
i,j,c=0,len(a)–1,0
while i<=j:
m =(i+j+1)//2
if a[m]>=key :
i=m+1
else:
j=m-1
c+=1
列表a =[23,21,19,18,16,15,14,11]，该程序段执行后，下列说法不正确的是（ ）
A.i的值为j+1 B.i的值可能是8
C.j的值可能是5 D.c的值一定是3
B
运用激活
Yunyong jihuo
考点小结
真题实践
分析考法
选对方法
高效突破
03
练一练
1.某二分查找算法的Python程序段如下：
d = [11,19,25,33,47,58]
i,j = 0,5
flag = int(input())
while i<=j and f==False:
m=(i+j)//2
if key==d[m]:f=True
if keyj=m-1
else:
i=m+1
运行该程序后输入key值为“33”，运行程序结束后下列说法不正确的是（ ）
A.变量f的值为True B.变量i的值为4 C.变量j的值为4 D.变量m的值为3
练一练
2.有如下VB程序段：
key＝int(input(″请输入待查数据：″))
s，i，j＝0，0，6
while i <＝ j：
m＝(i＋j)//2
s＝s＋m
if a[m]>Key：
j＝m－1
else：
i＝m＋1
print(s)
数组元素a[0]到a[6]的值依次为“12，15，18，20，20，20，29”，输入待查数据，执行该程序段后，则程序输出的结果不可能的是(　　)
A.7 B.9 C.15 D.17

展开更多......

收起↑