5.4 数据查找——二分查找 课件 2023—2024学年浙教版(2019)高中信息技术选修1

二分查找 比中间数小 Key 与中 间位置的 数 比 比中间数大 二分查找思想 m=(i+j)//2 m =(i+j+1)//2 每次d[m]与Key比较会确定下一次查找范围 d[m]<key 右半区间： i=m+1 d(m)]>key 左半区间： j=m-1 如：用数组d存放升序的数字序列 i表示查找范围第一个数组元素下标 (起始位置) j表示查找范围最后一个数组元素下标 (终止位置) m 表示查找范围内中间位置数组元素的下标 (中间位置) 二分查找思想 — (i+j /2 i=0 M=(i+j8//2 j=1QM=(i+j)//2 j=15 第1次比较： Ke 第子次[比] 较第2次比较： Key>d[m] 查找范围：d[8eyd[d5m]查找倒断：!d[8]~d[10] Key=52 j不 变 ，i=M+1=8 i不变，j=M-1 ①变 量i和j记录所要查找范围的起始和终止位置 ②计算中间点M 的位置： M=(i+j)//2 ③比较key和d(M) 的值，根据结果重新确定查找的起始和终止位置 或者直接告诉已经找到 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 15 17 18 22 27 35 45 48 52 65 67 72 85 97 98 二分查找思想 d=[10,15,17,18,22,27,35,45,48,52,65,67,72,85,97,98] key=int(input(”请输入想要查找的数字：”)) f=False en(d)- 1 s="查找过程" while i<=j: m=(i+j)//2 if d[m]==key: f=True b=m break s= r(atml) 5=s+¹,"+str(dtim) if f==True: print(" 查找成功!第"+str(b+1)+" 个") print(s) else: print("没有找到!") else: elif t : " d s k 二分查找程序实现 查找次数 搜索区间 中点 查找键与中点关系 i j 0 15 第一次 d[0]~d[15] 7 key>d[m] 8 15 第二次 d[8]~d[15] 11 key<d[m] 8 10 第三次 d[8]~d[10] 9 key=d[m] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 15 17 18 22 27 35 45 48 52 65 67 72 Qh O0 97 98 二分查找程序实现 Key=52 查找次数 搜索区间 中点 查找键与中点关系 i j 0 15 第一次 d[0]~d[15] 7 key>d[m] 8 15 第二次 d[8]~d[15] 11 key<d[m] 8 10 第三次 d[8]~d[10] 9 key>d[m] 10 10 第四次 d[10]~d[10] 10 key<d[m] 10 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 15 17 18 22 27 35 45 48 52 65 67 72 85 97 98 二分查找程序实现 Key=55 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 5 17 18 22 27 35 45 48 52 65 67 72 85 97 98 45 18 67 27 52 22 3 5 48 65 85 72 97 98 二分查找程序实现 15 10 17 Key=55 2 3 4 5 8 9 10 m=(i+j+1)//2 二分查找程序实现 m=(i+j)//2 1 5 8 9 4 6 5 1 2 3 4 5 6 7 8 9 10 m=(i+j+1)//2 二分查找程序实现 m=(i+j)//2 (9 8 10 3 ② 10 2 3 6 1 1 数组元素a[0]到a[7]的值分别是“11,22,33,44,55, 66,77,88”。若该程序运行结束后，CS的值为2,则key 可能的值是( B ) A.33或77 B.22或66 C.22或77 D.33 或66 某二分查找的程序段如下： i=0 j=7 Cs=0 while i<=j: CS=Cs+1 m=(i+j)//2 if a[m]==key: break elif a[m]<key: i=m+1 else: 二分查找练习 j=m-1 已知输入a[0]至a[7]的值依次为“88,79,62,55,46,31,20,1”,查找某key值的程序段如下： i=0;j=7;n=0 key=int(input()) while i<=j: m=(i+j)//2 if key==a[m]: break elif key>a[m]: j=m-1;n-=1 else: i=m+1;n+=1 print(n) 当输入不同的key值，运行该程序后，输出的不同结果共有( D ) A.5 种 B.6 种 C.7 种 D.8 种 二分查找练习 某段程序如下： a=[88,83,78,62,60,54,53,41,32,26] ans=[];i=0;j=9 key=int(input("请输入待查数据：") flag=False while i<=jand not flag: m=(i+j+1)//2 ans.append(a[m]) if a[m]==key: flag=True elif a[m]<key: j=m-1 else: i=m+1 print(ans) 执行该程序后，当输入的key 值为83时，输出的结果是( B ) A.[54,83] B.[54,78,83] C.[54,62,83] D.[60,78,83] 二分查找练习 现有一段查找程序如下： i=0;j=9; key=int(input()) while i<j: m=(i+j)//2 if ① j=m-1 else: i=m+1 print( ② ) B.①key>=a[m]②j+1 D.①key>a[m]②j+1 已知数组a 的10个元素分别为“88,79,79,79,31,31,31,31,1,1”,输入查找的key值，要查找第一个等于key的元 素下标并输出，则下列选项中关于程序划线处的代码描述，正确的是( B ) A.①key>a[m]②j C.①key>=a[m]②j 二分查找练习 $$