资源简介

(共19张PPT)
数据查找
情景导入1
打乱的扑克牌
请在打乱的扑克牌中寻找出下面这张牌，讲一讲你寻找的方法
查找（Search）又称检索，是计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。
查找的定义
常用查找算法：
顺序查找和对分查找
顺序查找——算法思想
算法思想
顺序查找又称线性查找，从顺序表的一端开始，依次将每个元素的关键字与给定值key（查找键）进行比较。
若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。
在不考虑扑克牌花色的情况下，仅在A到K,13张扑克牌中寻找指定的牌。扑克牌2～ 10 为数字本身,A 为 1 ,J 为 11 ,Q 为 12 ,K 为 13，变量Key存储要查找的牌。
顺序查找——算法描述
将代表13张扑克牌对应的数字存储于数组d中， 要查找的扑克牌对应数字储于变量key中。
② 依次将d数组中元素与key进行比较。
③ 若数组中某个数与key相等则查找成功并结束查找，若所有元素比较完毕仍找不到，则查找失败。
枚举算法
顺序查找——算法演示
d[0] d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] d[9] d[10] d[11] d[12]
11 12 13 4 10 6 7 8 9 5 1 2 3
key=4
①i=0，d[0]=11 !=key
②i=1，d[1]=12 !=key
③i=2，d[2]=13 !=key
④i=3，d[3]=4 ==key→查找成功
问题：
若将上述问题规模扩大，在n张牌中寻找，则最理想情况是查找_______次？最差的情况需要查找________次？平均查找次数：________
1
n
(n+1)/2
顺序查找——程序实现
For i in range(___________):
If :
________________
else:
________________
0,n,1
d[i]==key
print(i)
①遍历数组的索引。
②如果找到，输出下标，结束查找。
③若找不到，提示“没找到”
break
print(“没找到”)
顺序查找——小结
1.顺序查找本质上是一种__________思想，顺序查找程序就是用循环来枚举所有要查找的对象，然后在循环体内用条件判断当前枚举出的对象是否等于查找对象。
2.当需要查找的数据规模为 n 时，顺序查找最少查找____ 次，最多查找_____次，其平均查找次数是________。
3.顺序查找最大的优点是查找的数据可以是乱序的，但是其缺点是查找效率太低。顺序查找将待查找的数值与序列中的数逐个进行比较，直到找出与给定数值相同的数为止，其时间复杂度为_____ 。
枚举算法
1
n
(1+n)/2
O(n)
新打开的扑克牌
请在新打开的扑克牌中寻找出下面这张牌，讲一讲你寻找的方法
情景导入2
对分查找——算法思想
算法思想
首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，则根据数组的有序性，确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。
对分查找——算法描述
将13张扑克牌对应的数字（升序）存储于数组d中， 要查找的扑克牌对应数字储于变量key中。
② 依次将d数组查找区间中间位置的数mid与key进行比较。
③ 若mid与key相等则查找成功，结束查找,若key大于mid下一次查找区间为右半部分，反之为左半部分。重复②③两个步骤直到区间元素个数为零，即查找失败。
在不考虑扑克牌花色的情况下，仅在A到K,13张升序排列的扑克牌中寻找指定的牌。扑克牌2～ 10 为数字本身,A 为 1 ,J 为 11 ,Q 为 12 ,K 为 13，变量Key存储要查找的牌。
对分查找——算法演示
d[0]
d[1]
d[2]
d[3]
d[4]
d[5]
d[6]
....
d[12]
←i
←j
←mid
第1次查找：
范围为__________，i=________，j=_____，mid=___________。d[mid]=__________。
d[mid]_____key=5？
:后续查找的范围应该是_______________。
d[0]~d[12]
0
12
(0+12)//2=6
d[6]=7
>
d[0]~d[5]
1
2
3
4
5
6
7
...
13
i：查找数组的起点索引值；
j：查找数组的终点索引值；
mid=（i+j）//2，查找数组的中间位置的索引值。
对分查找——算法演示
d[0]
d[1]
d[2]
d[3]
d[4]
d[5]
←i
←j
←mid
第2次查找：
范围为__________，i=________，j=_____，mid=___________。d[mid]=__________。
d[mid]_____key=5？
:后续查找的范围应该是_______________。
d[0]~d[5]
0
5
(0+5)//2=2
d[2]=3
<
d[3]~d[5]
1
2
3
4
5
6
对分查找——算法演示
d[3]
d[4]
d[5]
←j
←mid
第3次查找：
范围为__________，i=________，j=_____，mid=___________。d[mid]=__________。
d[mid]_____key=5？
查找成功，结束查找。
d[3]~d[5]
3
5
(3+5)//2=4
d[4]=5
==
4
5
6
←i
对分查找——流程图描述
开始
i=0,j=12
d[mid]=key
d[mid]查找成功
查找失败
结束
Y
N
Y
N
Y
N
mid
i<=j
=(i+j)//2
i=mid+1
j=mid-1
对分查找——程序实现
key=int(input())；f=False；i=0 #所有数据（升序）存储在数组d中
j=
while :
mid=
if d[mid]==key:
f=True
break
if d[mid]>key:
else:
if f==True:
print("查找成功！下标为"+str(mid))
else:
print("没有找到！")
i<=j
(i+j)//2
j=mid-1
i=mid+1
①给i,j赋初值
②当i<=j时表示区间内元素个数不为零，重复执行查找工作
③计算查找区间中间位置mid
④判断中值是否就是查找键key
⑤如果中值不是查找键，则判定下一个查找范围应该在左半部分还是在右半部分。注意i和j的控制。
⑥输出查找结果：f=True,mid中存储的即为查找键Key在数组 d中的位置，f=False表示查找键key在数组d中不存在。
len(d)-1
对分查找——二叉排序树
7
3
1
5
4
6
2
10
8
9
12
11
13
二叉排序树：
①若左子树不为空，则左子树的值均小于它的根节点的值.
②若右子树不为空，则右子树的值均大于它的根节点的值
③它的左右子树也分别为二叉排序树。
13张扑克牌使用对分查找过程我们可以用一棵二叉树来表示。
假设对分查找数据规模为n最多查找次数？
最多查找次数为二叉数高度：int(log2n)+1。
查找算法小结
查找算法 顺序查找 对分查找
优点 ①算法简单，对数据是否有序没有要求。 ②查找效率高，适用于大数据查找。
缺点 ②查找效率较低，当数据量大时不宜使用。 ①要求被查找数据必须有序。
查找次数 一般情况是，当需要查找的数据规模为 n 时，顺序查找最少查找____次，最多查找____次，其平均查找次数是________。 当需要查找的数据规模为 n 时，最少查找 次，最多进行_____________次查找。
算法思想 顺序查找本质上是一种_______算法思想。 对分查找思想符合_______算法的思想。
1
n
(n+1)/2
int(log2n)+1
枚举
递归
1
查找的定义。
课堂小结
顺序查找算法思想、程序实现。
对分查找算法思想、程序实现。
顺序查找与对分查找算法的优缺点。

展开更多......

收起↑