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

(共19张PPT)
二分查找
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
keyj=m-1
二分查找又称折半查找，仅适用于有序表
二分查找
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
keyj=m-1
二分查找又称折半查找，仅适用于有序表
二分查找
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
二分查找又称折半查找，仅适用于有序表
二分查找
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，查找成功
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遍比较：
二分查找的程序实现
①存储待查找数据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("没有找到！")
⑥输出查找结果
二分查找的程序实现
①存储待查找数据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 keyj=m-1
else:
i=m+1
if f==True:
print("查找成功！第"+str(b+1)+"个数据")
else:
print("没有找到！")
二分查找查找效率
N:
1
经过x次除以2
1*2*2*……*2=N
乘了x个2
x=[log2N]
对分查找的最多查找次数是[log2N]+1
B
B
A
知识小结：
1. 二分查找算法的基本思想，适用范围；确定查找区间中点m的位置；
2.总结查找键key值与d[m]比较的三种情况。
感谢大家聆听