对分查找　【高效备课精研+知识精讲提升】 浙教版（2019）高中信息技术选修1

CHZX5.5对分查找浙江省高中信息技术选择性必修一《数据与数据结构》昌化中学应彤鑫考点剖析题号2016.42016.112017.42017.112018.42019.42020.12020.72020.72021.12021.61信息的概念会声会影信息安全道德信息的概念信息的概念信息的概念信息处理描述信息与信息处理信息与信息处理信息和信息技术基本概念信息和信息处理基本概念2smtp协议网页URL等网页html等浏览相关协议等浏览相关协议等电子邮局协议人工智能网页与浏览器网页与浏览器信息安全网页与浏览器基本概念3OCR操作应用人工智能、OCRWord批注修订人工智能OCR操作应用人工智能数据库相关知识数据表数据类型数据表数据类型数据表名称、字段、数据类型Access数据库（数表名称、数据类型、导出到Excel）4数据表操作知识数据表（设计视图）内码、进制转换数据库相关知识数据库相关知识数据表相关知识计算机信息编码进制转换进制转换信息编码相关知识进制转换与ASCII码5流程图执行结果流程图执行结果数据表操作的说法流程图执行结果字符内码进制转换PS基本操作PS基本操作Photoshop基本操作GoldWave声音处理Photoshop图像处理6会声会影进制转换流程图执行结果进制转换GoldWave流程图执行结果视频数字化压缩比声音容量计算声音容量计算图像容量计算、压缩比图像存储容量计算7进制转换GoldWav作品规划制作脚本GoldWav流程图执行结果GoldWaveIf语句变式VB表达式VB算术表达式VB算术表达式VB算术表达式8PS基本操作PS基本操作GoldWavePS基本操作PS基本操作PS基本操作流程图执行结果流程图执行结果流程图执行结果流程图执行结果流程图执行结果9Flash基本操作Flash_按钮Flash_补间属性Flash基本操作Flash_按钮Flash_按钮操作冒泡排序交换次数For循环程序执行结果(字符串)For循环程序执行结果(字符串)枚举算法应用（选择填空）枚举算法应用（选择填空）10图像数字化图像数字化视频数字化图像容量比视频数字化图像数字化For循环程序执行结果Do循环程序选择填空Do循环程序选择填空字符串相关运用对分查找算法变式11排序算法_For对称字符串For程序对分查找For程序结果For程序结果Do循环程序结果程序功能代码排序对分查找对分查找冒泡排序算法字符串处理结果12对分查找对分查找选择排序改进对分查找对分查找对分查找对分查找冒泡排序变式冒泡排序变式对分查找冒泡排序算法及其变式考点剖析对分查找通过实例分析，掌握对分查找的基本思想和程序实现。借助对分查找的基本实现，实现对分查找变式的应用。理解对分查找的应用场景，能在实际问题解决中运用对分查找。目标分解基础落实算法思想经典程序01基础落实Jichuluoshi算法思想首先将查找数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找数不同，则根据有序性，确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。①要求被查找数据必须有序。②查找效率非常高，适用于大数据查找。算法特点算法设计开始i=0,j=9d[m]=key?d[m]<key?查找成功查找失败结束YNYNYNm=i<=j(i+j)//2i=m+1j=m-1基础落实Jichuluoshi算法描述key=int(input())d=[10,15,17,18,22,27,35,45,48,52]f=Falsei=0j=

while

:m=

ifd[m]==key:f=Truebreakifd[m]>key:

else:

iff==True:print("查找成功！下标为"+str(m))else:print("没有找到！")i<=j(i+j)//2j=m-1i=m+1①给i,j赋初值：i查找的起点

j查找的终点②当i<=j时，重复执行查找工作③对分，当前查找的中间值m④判断中值是否就是查找键⑤如果中值不是查找键，则判定下一个查找范围应该在前半部分还是在后半部分。注意i和j的控制。⑥输出查找结果len(d)-1基础落实Jichuluoshi代码变式一：中间值变化key=int(input())d=[10,15,17,18,22,27,35,45,48,52]f=Falsei=0j=len(d)-1whilei<=j:

m=(i+j)//2ifd[m]==key:f=Truebreakifd[m]>key:j=m-1else:i=m+1iff==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)基础落实Jichuluoshi代码变式一：中间值变化基础落实Jichuluoshi中间值[0,8][0,9]m=(i+j)//244m=int(（i+j）/2)44m=int(（i+j）/2+0.5)45m=（i+j+1）//245m=int(（i+j+1）/2)45m=round(（i+j）/2)45代码变式二：增加一些变量i=0j=len(d)-1whilei<=j:m=(i+j)//2ifd[m]==key:breakifd[m]>key:j=m-1else:i=m+1c+=1功能：用于统计查找次数s=“L”或s=s+”L”功能：用于记录变化过程s=“R”或s=s+”R”功能：用于记录变化过程基础落实Jichuluoshi代码变式三：找到不结束i=0j=len(d)-1whilei<=j:m=(i+j)//2ifd[m]==key:breakifd[m]>key:j=m-1else:i=m+1ifd[m]>key:j=m-1else:i=m+1ifd[m]>=key:j=m-1else:i=m+1基础落实Jichuluoshi下标0123456789值8172430364055586166①imjIfd[m]==key:

f=Trueifd[m]>key:j=m-1else:i=m+1运用激活经典再现考法分类例题实践02运用激活Yunyongjihuo经典再现【例1】某二分查找算法的Python程序段如下：a=[8,17,24,30,36,40,55,58,61,66]key=int(input())i,j=0,9res=[]whilei<=j:m=(i+j+1)//2ifkey==a[m]:breakelifkey<a[m]:

j=m-1else:i=m+1res.append(a[m])print(res)执行该程序段，当输入的值为30时，程序输出结果为（

）A.[40,24] B.[40,24,36] C.[24,36]

D.[36,17,24]考点：查找路径核心：快速定位中间值m方法：表格法B下标0123456789值8172430364055586166①imj②imj③ijm运用激活Yunyongjihuo变式训练【变式训练1】有如下python程序段：key=int(input("请输入待查数据值："))d=[17,18,20,23,24,25,28,32,34,35]s="";i=0;j=len(d)-1whilei<=j:m=(i+j)//2s=s+""+str(d[m])ifkey<d[m]:j=m-1else:i=m+1print(s)输入待查数据值为20，执行该程序段，则输出的结果是（）A．24182023 B．241820 C．2520 D．252023A运用激活Yunyongjihuo经典再现【例2】某二分查找算法的程序如下：i,j＝0,7n＝0whilei<＝j：n＝n＋1m＝(i＋j)//2ifkey＝＝d[m]：breakelifkey>d[m]：j＝m－1else：i＝m＋1数组元素d[0]到d[7]的值依次为″83，75，62，41，33，27，16，2″，若运行该程序段后，n的值为2，则key的值可能是(

)A.62或16 B.62或27C.75或27 D.75或16C考点：查找次数核心：快速定位中间值m方法：二叉树法417527运用激活Yunyongjihuo变式训练【变式训练2】某二分查找算法的程序如下：i=0j=9c=0whilei<=j:c+=1m=(i+j)//2ifa[m]<key:i=m+1else:j=m-1print(c)数组元素a的值依次为″2,13,13,14,23,26,29,31,32,38″，若运行该程序段后，c的值为3，则key的值不可能的是(

)

A.11

B.13C.29

D.32C运用激活Yunyongjihuo经典再现【例3】有如下python程序段：a=[11，22，33，44，55，66]i=0:j=5:p=0key=23whilei<=j:p+=1m=(i+j)//2ifa[m]==key:

breakifa[m]>key:

j=m-1else:i=m+1对数组a中6个有序数据“11，22，33，44，55，66”，用上述程序代码查找数据“23”，程序执行完毕后，下列各变量值正确的是()A．i=2 B．j=2 C．m=2 D．p=2A考点：变量的值核心：模拟查找过程方法：表格法运用激活Yunyongjihuo变式训练【变式训练3】某算法的VB程序段如下:key=randint(0,3)*2+13i,j,c=0,len(a)–1,0whilei<=j:m=(i+j+1)//2ifa[m]>=key:i=m+1else:j=m-1c+=1列表a=[23,21,19,18,16,15,14,11]，该程序段执行后，下列说法不正确的是（

）A.i的值为j+1

B.i的值可能是8

C.j的值可能是5

D.c的值一定是3B运用激活Yunyongjihuo考点小结常见考点查找次数二叉树法查找路径表格法变量的值表格法增加变量真题实践分析考法选对方法高效突