资源简介

(共27张PPT)
思考
生活中的查找
1、如何在一堆试卷中查找到自己的那一张试卷？
2、如何从一本相册中查找到自己所需的那一张？
3、如何在一车的旅客中查找到携带违禁品的旅客？
CHZX
5.4 数据查找
浙江省高中信息技术 选择性必修一 《数据与数据结构》
顺序查找
算法思想
程序实现
01
顺序查找
Shunxu chazhao
算法思想
从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。若某个数据与给定值相等，则查找成功，记录所查数据的位置；反之，则查找不成功。
①算法简单，对数据是否有序没有要求。
②查找效率较低，当数据量大时不宜使用。
算法特点
顺序查找
Shunxu chazhao
算法演算
d[0] d[1] d[2] d[3] d[4] d[5]
43 56 23 15 50 78
在数组序列d=[43,56,23,15,50,78]中，查找关键字key为15的元素
key=15
①i=0，d[0]=43 !=key
②i=1，d[1]=56 !=key
③i=2，d[2]=23 !=key
④i=3，d[3]=15 ==key→查找成功
问题：
若要查找的内容在n个数据中，则最理想情况是比较_______次？最差的情况需要比较________次？
1
n
顺序查找
Shunxu chazhao
算法演算
d[0] d[1] d[2] d[3] d[4] d[5]
43 56 23 15 50 78
在数组序列d=[43,56,23,15,50,78]中，查找关键字key为80的元素
key=80
①i=0，d[0]=43 !=key
②i=1，d[1]=56 !=key
……
⑥i=5，d[5]=78 !=key
问题：
若要查找的内容不在n个数据中，则当i=________时，需反馈查找失败？
n
d[6]
⑦i=6，查找失败
顺序查找
Shunxu chazhao
程序实现
For i in range(___________):
If :
________________
else:
__________________
0,n
d[i]==key
print(i)
print(“没找到”)
①从0到n-1逐一比较
②如果找到，输出下标
③若找不到，提示失败
问题：
若找到元素，后续的比较是否还有必要进行？（假设就一个元素符合条件）
break
顺序查找
Shunxu chazhao
程序实现
Flag=False
for i in range(0，n):
if d[i]==key:
flag=Ture
break
if flag:
print(i)
else:
print(“没找到”)
找到/找不到，两种状态，利用一个逻辑型的变量flag来表示是否找到，没找到(False)继续找，找到了(True)就结束。
练一练
1、顺序查找算法的部分代码如下：
Flag=False
i=0
while i<5 and Flag==False:
i=i+1
if a[i]==key :
Flag=True
if Flag==False :
i=0
数组元素a=[8,7,3,5,4]，若key值为3，则运行该程序后，变量i的值是（ ）
A.0 B.2 C.3 D.5
B
练一练
2、某查找算法的VB代码如下：
k=0
i=0
while i<=6:
if a[i]==key :
k=i
i=i+1
数组元素a=[5,3,5,1,8,5,9]，当变量key值为5时，运用该算法处理后，变量k的值是( )
A.1 B.2 C.5 D.0
C
练一练
3.某查找算法的VB代码如下：
k=0
i=0
while i<=6:
if a[i]==key :
k=i
break
i=i+1
数组元素a=[5,3,5,1,8,5,9]，当变量key值为5时，运用该算法处理后，变量k的值是( )
A.1 B.2 C.5 D.0
D
思考
现有1~100共100个数字，且这100个数字按顺序升序排列，待查找数key是这其中的一个，如何快速找到这个key？
对分查找
算法思想
程序实现
02
对分查找
Duifen chazhao
算法思想
首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，则根据有序性，确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。
①要求被查找数据必须有序。
②查找效率非常高，适用于大数据查找。
算法特点
对分查找
Duifen chazhao
算法演算
用数组d存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=48？
d[0]
d[1]
d[2]
d[3]
d[4]
d[5]
d[6]
d[7]
d[8]
d[9]
←i
←j
←mid
第1次查找：
范围为__________，i=________，j=_____，mid=___________。d[mid]=__________。
d[mid]_____key？
∴后续查找的范围应该是_______________。
d[0]~d[9]
0
9
(0+9)//2=4
d[4]=22
<
d[5]~d[9]
对分查找
Duifen chazhao
算法演算
用数组d存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=48？
d[5]
d[6]
d[7]
d[8]
d[9]
←i
←j
←mid
第2次查找：
范围为_____________，i=________，j=_____，mid= ___________ 。d(mid)=______。
d(mid)_____key？
∴后续查找的范围应该是_______________。
d[5]~d[9]
9
5
(5+9)//2=7
45
<
d[8]~d[9]
d[0]
d[1]
d[2]
d[3]
d[4]
d[5]
d[6]
d[7]
d[8]
d[9]
←i
←j
←mid
对分查找
Duifen chazhao
算法演算
用数组d存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=48？
d[5]
d[6]
d[7]
d[8]
d[9]
←i
←j
←mid
d[0]
d[1]
d[2]
d[3]
d[4]
d[5]
d[6]
d[7]
d[8]
d[9]
←i
←j
←mid
48
52
d[8]
d[9]
←i
←j
←mid
第3次查找：
范围为_____________，i=________，j=_____，mid=___________。d(mid)=______。
d(mid)_____key？
d[8]~d[9]
8
9
(8+9)//2=8
48
=
提示查找成功
对分查找
Duifen chazhao
算法演算
用数组d存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=48？
d[0]
d[1]
d[2]
d[3]
d[4]
d[5]
d[6]
d[7]
d[8]
d[9]
第一次查找：d[0]~d[9]，i=0，j=9，mid=4，d[mid]第二次查找：d[5]~d[9]，i=5，j=9，mid=7，d[mid]第三次查找：d[8]~d[9]，i=8，j=9，mid=8，d[mid]=key
思考
①若d[mid]②i和j是如何变化的？
③若查找的值是52，最终i、j、mid的值为多少？
后半
i=mid+1，j不变
i、j、mid相等
对分查找
Duifen chazhao
算法演算
用数组d存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=17？
d[0]
d[1]
d[2]
d[3]
d[4]
d[5]
d[6]
d[7]
d[8]
d[9]
第一次查找：d(1)~d(10)，i=1，j=10，mid=5，d(mid)>key
第二次查找：d(1)~d(4)，i=1，j=4，mid=2，d(mid)第三次查找：d(3)~d(4)，i=3，j=4，mid=3，d(mid)=key
思考
①若d(mid)>key，则新查找的范围为______部分（前半/后半）
②若d(mid)>key ,i和j是如何变化的？
前半
i不变，j=mid-1
对分查找
Duifen chazhao
算法演算
用数组d存放数组序列，用i表示查找范围的第一个数组元素下标，用j表示最后一个数组元素下标。假如查找键key=20？
d[0]
d[1]
d[2]
d[3]
d[4]
d[5]
d[6]
d[7]
d[8]
d[9]
10
15
17
18
d[0]
d[1]
d[2]
d[3]
←i
←j
←mid
17
18
d[2]
d[3]
←i
←j
←mid
18
d[3]
←i,j,mid
思考
继续进行查找的条件是什么？在什么情况下查找会结束？
当i<=j时，重复查找。
①找到数据，查找结束；②i>j时，找不到数据，查找结束。
←i
←j
←mid
对分查找
Duifen chazhao
算法演算
数组 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
值 2 9 11 15 18 26 29 30 38 49
查找次数
3
1
4
3
2
3
4
3
2
4
对分查找的查找效率
10个数进行对分查找算法，则平均查找次数： 次。
对分查找最多查找次数： 次。
2.9
Log2n+1
对分查找
Duifen chazhao
算法演算
（1）key与d[mid]的大小比较影响i，j在后续查找中的取值。
①若d[mid]②若d[mid]>key，则j=mid-1，i不变
（2）继续重复进行查找的条件。
当i<=j时
（3）对分查找最多的查找次数(n个数据)。
最多次数=Int(log2n)+1
∵n个数据对分x次最后变为1个数据
∴n*(1/2)^x=1
∴x=log2n
∵最后一个数据还要参与一次查找
∴最多次数=Int(log2n)+1
练一练
1.用对分查找从数列3、6、7、10、12、16、25、30、75中查找数据10，则依次访问的数据为( )
A. 12、6、7、10 B.12、7、10
C.12、6、10 D.12、7、6、10
A
数组 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
值 3 6 7 10 12 16 25 30 75
m1
m2
m3
m4
对分查找
Duifen chazhao
算法演算
开始
i=0,j=9
d[mid]=key
d[mid]查找成功
查找失败
结束
Y
N
Y
N
Y
N
mid=
i<=j
(i+j)//2
i=mid+1
j=mid-1
对分查找
Duifen chazhao
程序实现
key=int(input())
d=[10,15,17,18,22,27,35,45,48,52]
f=False
i=0
j=
while :
m=
if d[m]==key:
f=True
break
if d[m]>key:
else:
if f==True:
print("查找成功！下标为"+str(m))
else:
print("没有找到！")
i<=j
(i+j)//2
j=m-1
i=m+1
①给i,j赋初值，
②当i<=j时，重复执行查找工作
③对分，取中值m
④判断中值是否就是查找键
⑤如果中值不是查找键，则判定下一个查找范围应该在前半部分还是在后半部分。注意i和j的控制。
⑥输出查找结果
len(d)-1
练一练
1. 某二分查找算法的程序如下：
i＝0
j＝7
n＝0
while i<＝ j ：
n＝n＋1
m＝(i ＋ j)//2
if key＝＝d[m]：
break
elif key > d[m]：
j＝m－1
else：
i＝m＋1
数组元素d[0]到d[7]的值依次为″83，75，62，41，33，27，16，2″，若运行该程序段后，n的值为2，则key的值可能是(　　)
A.62或16 B.62或27 C.75或27 D.75或16
C
练一练

展开更多......

收起↑