5.4.1 数据查找-教学设计 （表格式）

教学设计 课程基本信息 课题 5.4 数 据 查 找 （二）———二 分 查 找 教学目标 1.通过猜价格，能理解二分查找的算法思想。 2.通过查询VIP号， 能合理选用数据结构，理解二分查找的范围与条件。 3.能熟练应用自然语言、流程图、Python语言、二叉树实现二分查找。 4.能熟练应用二分查找算法，解决生活、学习中的问题。 指向的核心素养 ●信息意识：学生能够结合实例，自觉、主动地有意识地选择恰当的数据结构表达数据比较与处理信息。 ●计算思维：学生能够结合实例，抽象问题的基本特征，设计算法与数据结构，编程解决问题。 ●数字化学习与创新：要使学生较为熟练地运用二分查找解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。 ●信息社会责任：自觉遵守相应的伦理道德和法律法规。 教学内容 教学重点： 1. 二分查找的算法思想。 2. 能熟练应用自然语言、流程图、Python语言、二叉树实现二分查找。 教学难点： 能熟练应用二分查找算法，解决生活、学习中的问题。 教学过程 情景引入 猜一猜：小明的计时手表多少money？ 已知前提：价格20-80元？ 二分查找概念： 二分查找（binary search）又称折半查找，对分查找。 它是一种效率很高的查找方法，但被查找的数据序列必须是有序的。 三、二分查找算法思想： ①将查找键与有序数组内处于中间位置的元素进行比较； ②如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找 ③在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 四、二分查找实践体验： 五、用Python语言编写程序并调试： d=[6,12,15,18,22,25,28,35,46,58] key=int(input(“输入待查找元素：”)） f=False i = 0 # i和j定义子数组的边界，一开始搜索的是整个数组 j = len(d)-1 while i <= j: m = (i+j) //2 if d[m] == key: f=True b=m break if key < d[m]: # 到左边去找 j = m-1 else: # 到右边去找 i = m + 1 if f==True: print("查找成功！第"+str(b)+"个") else: print("没有找到！") 六、二分查找的递归实现: def bsearch(k,dat,i,j): if i>=j+1: # 递归结束条件1 print("未找到！") # 递归结束值1 return m = (i+j) //2 if dat[m] == k: # 递归结束条件2 print("找到了！第"+str(m+1)+"个" ) # 递归结束值2 return elif k < dat[m]: # 到左边区间去找 return bsearch(k,dat,i,m-1) # 递归表达式，自己调用自己 elif k >= dat[m]: # 到右边区间去找 return bsearch(k,dat,m+1,j) # 递归表达式，自己调用自己 #主程序 d=[6,12,15,18,22,25,28,35,46,58] print(d) key=int(input("输入待查找元素：")) i=0;j=len(d)-1 bsearch(key,d,i,j)#调用bsearch函数 七、顺序查找、二分查找对比 八、二分查找判定树：二叉树 1、中点位置绘制 2、中点值绘制 九、生活实战应用：某校期中考试部分学生信息技术与通用技术成绩如右表所示，查询某赋分数的所有学生名单，并输出共有几个同分数的学生，要求实现以上功能，如查询不到则显示“无此分数的学生”。请编程实现。 ... ...