5.4 数据查找——二分查找　课件 2022—2023学年高中信息技术浙教版（2019）选修1 数据与数据结构

二分查找 更多模板请关注：https://haosc.tukuppt.com 1 14 二分查找 0 1 2 3 4 5 6 7 8 9 10 d 6 12 15 18 22 25 28 35 46 58 60 j=len(d)-1 i=0 m=(i+j)/2 key 12 key<m，所以只能在左边查找 j=m-1 二分查找又称折半查找，仅适用于有序表 3 二分查找 0 1 2 3 4 5 6 7 8 9 10 d 6 12 15 18 22 25 28 35 46 58 60 j i m=(i+j)/2 key 12 key<m，所以只能在左边查找 j=m-1 二分查找又称折半查找，仅适用于有序表 4 二分查找 0 1 2 3 4 5 6 7 8 9 10 d 6 12 15 18 22 25 28 35 46 58 60 j i m=(i+j)/2 key 12 key>m，所以只能在右边查找 i=m+1 二分查找又称折半查找，仅适用于有序表 5 二分查找 0 1 2 3 4 5 6 7 8 9 10 d 6 12 15 18 22 25 28 35 46 58 60 j i m=(i+j)/2 key 12 二分查找又称折半查找，仅适用于有序表 key=m，查找成功 6 7 C C 二分查找 二分查找又称折半查找，对分查找。它是一种效率很高的查找算法，但被查找的数据序列必须是有序的。 6 12 15 18 22 25 28 35 46 58 60 i j 6 12 15 18 22 25 28 35 46 58 60 i j m 6 12 15 18 22 25 28 35 46 58 60 i j m 6 12 15 18 22 25 28 35 46 58 60 i j m 6 12 15 18 22 25 28 35 46 58 60 j i m 0 1 2 3 4 5 6 7 8 9 10 Key=12 开始： 第1遍比较： 第2遍比较： 第3遍比较： 第4遍比较： 10 二分查找的程序实现 ①存储待查找数据key等 key=12;f=False d=[6,12,15,18,22,25,28,35,46,58,60] ②i和j定义子数组的边界 i=0;j=len(d)-1 当存在待查找的子数组时，继续查找 ③确定本次查找的数据下标 本次查找的数据下标为i,j的中点 ④若找到则停止循环，记录位置 判断中点数据是否为key值： 找到记录下标;做找到标记 break 没找到时，若中点数据偏大： key应在中点左侧 没找到时，若中点数据偏小： key应在中点右侧 ⑤调整子数组范围继续查找 if f==True: print("查找成功！第"+str(b+1)+"个数据") else: print("没有找到！") ⑥输出查找结果 11 二分查找的程序实现 ①存储待查找数据key等 ②i和j定义子数组的边界 ③确定本次查找的数据下标 ④若找到则停止循环，记录位置 ⑤调整子数组范围继续查找 ⑥输出查找结果 key=12; f=False d=[6,12,15,18,22,25,28,35,46,58,60] i=0;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+1)+"个数据") else: print("没有找到！") 12 二分查找查找效率 N: 1 经过x次除以2 1*2*2*……*2=N 乘了x个2 x=[log2N] 对分查找的最多查找次数是[log2N]+1 B B A 知识小结： 1. 二分查找算法的基本思想，适用范围；确定查找区间中点m的位置； 2.总结查找键key值与d[m]比较的三种情况。 感谢大家聆听 19 Lavf58.20.100 Bilibili VXCode Swarm Transcoder v0.3.42_sync_fix $