5.4 数据查找 课件（28张PPT）

(共28张PPT)
选择性必修模块1《数据与数据结构》
第五章 数据结构与算法
5.4. 数据查找
新扑克牌
打乱后的扑克牌
情境导入
请在扑克牌中寻找出下面这张牌，讲一讲你寻找的方法
思考：
生活中还有哪些查找的具体例子，你是通过什么样的方法快速进行查找的。
查找（Search）又称检索，是计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。
算法
思想
②输入查找关键值key；
③从数组中的第一个元素开始与关键值key进行比较，若相等，则输出相应信息；否则，继续比较下一个元素。
①将待查找的数据储存在数组中；
④直到找完数组的最后一个元素仍不想等，输出查找失败。
顺序查找算法思想
查找动物问题
A数组中存放了一些动物名称“dog” “cat” “monkey” “tiger” “panda” “rabbit” “horse”，现在想查找动物“bear”是否在其中，如找到输出“查找成功！是第几个动物”，否则输出“查找失败”，无论查找成功与否都输出比较的次数。
返回
拓展提升
某个班级的部分学生语文成绩如下表所示，要求实现根据考号查询该生的语文成绩，如查询不到则显示“该班无此学生”。
思考：
用哪一种数据结构对表格数据进行存储？
对哪个字段进行顺序查找？
思考：
若一个班级一共有45人，查找成功最好情况是比较几次？最差呢？若查找不成功，需要比较几次？
若有N个数据，那顺序查找的平均比较次数为几次？
若一个数据序列有n个数，查找不成功的比较次数为n，查找成功：最好的情况为1次，最差的情况为n次，所以查找成功时的平均比较次数为(n+1)/2，且顺序查找的时间复杂度为O(n)
情境导入
猜数字游戏
观看视频，思考：
生活中“如何迅速的找到东西”？
二分查找
二分查找（binary search）又称折半查找，对分查找。
它是一种效率很高的查找方法，但被查找的数据序列必须是有序的。
算法
思想
②如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找
③在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。
①将查找键与有序数组内处于中间位置的元素进行比较；
二分查找算法思想
实践体验：
在数组d的11个元素中，已按增序存储了11个数据：6、12、15、18、22、25、28、35、46、58、60，如何用二分法查找数据12（已存储在变量key中）？
提示：
11个数据存储在d[0]到d[10]
Key=12
思考：
如何确定查找区间中点m的位置？
讨论：
查找范围（i,j）的变化情况？
将查找键key值与d[m]比较，结果必然是如下三种情况之一：
keykey=d[m] 找到了需要的数据。
key>d[m] 数组d递增，新的查找范围为（m+1，j）。
思考：若数组d递减，查找范围（i,j）如何变化？
情境导入
key=12
查找过程：
6 12 15 18 22 25 28 35 46 58 60
0 1 2 3 4 5 6 7 8 9 10
中点位置m的计算？
i、j的变化规律？
二分查找规律
中点位置 m=
keykey=d[m] 找到了需要的数据。
key>d[m] 由于与①相同的理由，必须在新的范围（m+1，j）中继续查找。
这样，除了出现情况②，在通过一次比较后，新的查找范围将不超过上一次查找范围的一半。
查找键key值与d[m]比较结果情况总结：
二分查找流程图
二分查找程序实现
d=[6,12,15,18,22,25,28,35,46,58,60]
f=False
# i和j定义子数组的边界，一开始搜索的是整个数组
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)+"个")
else:
print("没有找到！")
二分查找延伸——二叉树
从根结点到待查结点的一条路径为25→15→6→12，比较次数为4次。通过观察可知，在n个元素排序的顺序表里，某一次查找过程中，所做比较次数不超过判定树的高度加1，即
课堂小结
1. 二分查找算法的基本思想，顺序查找和二分查找的区别；
2. 二分查找算法的特点及适用范围；
3. 二分查找的基本方法，确定查找区间中点m的位置；
4. 查找键key值与d[m]比较的三种情况。
情境导入
航空公司VIP会员积分查询部分数据（Excel数据）
VIP号 姓名 飞行里程（KM） 积分
600214 韩江辉 16801 519
601278 蒋志来 5321 78
600815 李亚东 28745 436
607854 王庆生 1861 39
605719 李燕 7493 138
603532 王晓燕 6875 102
600101 郑煜明 14253 236
600087 蔡佳宁 112703 958
抽象与建模
返回
问题：从表中的数据可以看出，每个会员的信息是一条记录，包括VIP号、姓名、飞行里程、积分等数据项。根据刚才的实践体验，对记录快速查询会员积分，查找应当如何进行？
设计算法与数据结构
返回
数据查找算法有两种，哪种更适合？
查找可采用顺序查找算法或二分查找算法，对数据进行一次查找，采用顺序查找算法。对数据重复查找，二分查找算法的效率高于顺序查找算法，但二分查找提前：被查找的数据序列必须是有序，即在查找前要按VIP号为关键字进行排序。
程序实现
返回
import csv
#数据读入
csvFile = open("vip.csv", "r")
reader = csv.reader(csvFile)
a = []
for item in reader:
a.append(item)
csvFile.close()
#排序
def bubble_sort(d):
for i in range(1,len(d)):
for j in range(1,len(d)-i):
if int(d[j][0])>int(d[j+1][0]):
temp=d[j]
d[j]=d[j+1]
d[j+1]=temp
#二分查找
def bsearch(s,array):
i = 1 #查找范围不包含第一行数据
j = len(array)-1
while i <= j:
m = (i+j) //2
if int(array[m][0]) ==s:
return m
if s < int(array[m][0]):
j = m-1
else:
i = m + 1
return -1 #未找到返回-1
bubble_sort(a)
key=int(input('请输入要查询的VIP号：'))
m=bsearch(key,a)
if m !=-1:
print(a[m][1],"先生/女士，',您的积分为：",a[m][3])
else:
print('找不到VIP号对应的用户信息！')
记录的关键字
查找注意事项
查找算法的步骤
不同查找算法对
算法的实现影响
查找算法的效率
课堂小结
课堂作业
1.基础作业（面向所有学生）；
2.本节安排了三道题目，可以结合本章习题布置作业。