高中信息技术浙教版 (2019)选修1 数据与数据结构5.4 数据查找一等奖ppt课件

这是一份高中信息技术浙教版 (2019)选修1 数据与数据结构5.4 数据查找一等奖ppt课件，共22页。PPT课件主要包含了学习目标，猜一猜，第1次50，第2次40，第3次45，二分查找概念，二分查找算法思想，二分查找实践体验，mi+j2，二分查找规律等内容，欢迎下载使用。

能理解二分查找的算法思想。
能合理选用数据结构，理解二分查找的范围与条件。
能用自然语言、流程图、Pythn语言、二叉树实现二分查找。
能熟练应用二分查找算法，解决生活、学习中的问题。
阅读教材P137-141，可根据个性学习暂停或加速播放课程。
小明的计时手表多少mney？
已知前提：价格20-80元？
二分查找（binary search）又称折半查找，对分查找。它是一种效率很高的查找方法，但被查找的数据序列必须是有序的。
②如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找
③在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。
①将查找键与有序数组内处于中间位置的元素进行比较；
提示：（1） 10个数据存储在d[0]到d[9] （2）Key=12
此时i=0，j=3，m=1时，a[m]==key，找到结束查找。
在数组d的10个元素中，已按升序存储了10个数据：5、12、16、18、21、26、28、39、48、56，如何用二分法查找数据12（已存储在变量key中）？
如何确定查找区间中点m的位置？
m=（i+j+1)//2
查找范围（i,j）的变化情况？
将查找键key值与d[m]比较，结果必然是如下三种情况之一：
keykey=d[m] 找到了需要的数据。
key>d[m] 数组d递增，新的查找范围为【m+1，j】。
思考：若数组d递减，查找范围（i,j）如何变化？
keykey>d[m] 数组d递减，新的查找范围为【i，m-1】。
二分查找的流程图描述(升序序列中查找）：填一填
keyd[m] 与①相同的理由，必须在新的范围（m+1，j）中继续查找。这样，除了出现情况②，在通过一次比较后，新的查找范围将不超过上一次查找范围的一半。
查找键key值与d[m]比较结果情况总结：
二分查找Pythn程序实现:
d=[6,12,15,18,22,25,28,35,46,58]key=int(input(“输入待查找元素：”)）f=Falsei = 0 # i和j定义子数组的边界，一开始搜索的是整个数组j = len(d)-1while 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 + 1if 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)-1bsearch(key,d,i,j)#调用bsearch函数
顺序查找、二分查找对比
≈ lg(n+1)-1
二分查找判定树：二叉树
二分查找判定树：二叉排序树
找12：从根结点到待查结点的一条路径为21→12，比较次数为2次完成。
某校期中考试部分学生信息技术与通用技术成绩如右表所示，查询某赋分数的所有学生名单，并输出共有几个同分数的学生，要求实现以上功能，如查询不到则显示“无此分数的学生”。请编程实现。
#读取csv中的文件数据imprt csv #导入csv模块 f=pen("期中考技术成绩.csv",'r')#打开csv数据文件c=[]#定义空列表a r=csv.reader(f)#建立一个读入数据的对象rn=0#记录数初值fr i in r:#每一行为c列表一个元素,此元素为字符串 c.append(i)#从表中第一行开始依次读入到c列表中 n+=1 #记录数增加1f.clse#关闭csv数据文件print("从CSV中获得的数据：")fr i in range(len(c)): print(c[i]) #输出csv文件中读入的记录key=int(input("请输入要查找的分数："))i=1;j=len(c)-1#查找范围索引值的左右端点值while i<=j: #左端点i<=右端点j,继续二分查找 m=(i+j)//2 #计算中点索引值 if key=int(c[m][2])时 j=m-1 #在表的左区间找print("要查找的"+str(key)+"数据第一个位置是："+str(i))b=i #记录第一个位置到b中
#找第一个key所在的位置结束#找最后一个key所在的位置i=1;j=len(c)-1#查找范围索引值的初值与终值while i<=j:#左端点i<=右端点j,继续二分查找 m=(i+j)//2#计算中点索引值 if key<=int(c[m][2]):#表数据降序， i=m+1#在表的右区间找 else:#key>int(c[m][2])时 j=m-1#在表的左区间找print("要查找的"+str(key)+"数据最后一个位置是："+str(j))print("总共",key,"的个数为",j-b+1,"个")print(c[0])fr k in range(b,j+1): #输出所有key的人员信息 print(c[k])
查找区间i,j,m的位置
个数、不大于、不小于问题
查找键key值与d[m]比较
对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油）
1.某对分查找算法的 VB 程序如下：i = 0;j = 29m = (i + j) // 2while i <= j and key!=a[m]:If key > a[m]: i = m + 1 else: j = m – 1m = (i+j)// 2 # ①数组元素 a[0]到 a[29]各不相同且按升序排列，若查找键key与a[8]相等，执行该程序段，①处语句的执行次数是A.2B.3 C. 4 D.5