5.4.2 查找算法的应用 课件（34张PPT）

(共34张PPT)
5.4.2 查找算法的应用
1.老师请身高在165到170的同学排练舞蹈
2.到超市购买水笔
3.乘公交车刷卡付钱
查找算法 基本算法 操作基础
生活实例
VIP号 姓名 飞行里程（km）
积分
600214 韩江辉 16801
519
601278 蒋志来 5321
78
600815 李亚东 28745
436
…… …… ……
……
603692 赵新星 5321
78
600087 蔡佳宁 112703
958
不少航空公司都会提供优惠的会员服务，当某会员飞行里程累积达到一定数量 后，可以使用里程积分兑换奖励机票或奖励升舱等服务。现给定某航空公司VIP会 员的飞行里程、积分等信息，如下表所示，要求实现根据VIP号码快速查询会员积
实例分析 航空公司VIP会员积分查询
分的功能。
1.抽象与建模
记录 查找
1.按列存储 四个一维数组
vip xm lc jf
2.数据结构
jf[2]
xm
vip
[2]
[2]
[2]
lc
2.按行存储 一个一维数组 a
a[i]
a[2][0] a[2][1] a[2][2] a[2][3]
2.数据结构
顺序查找 查找效率低
二分查找 → 查找效率高
数据按VIP号有序
3.设计算法
查找算法
import csv
csvFile=open(" csv","r") reader=csv.reader(csvFile)
a=[]
for item in reader:
_____
csvFile
__
按行存储的一维数组a 二分查找算法
"vip.csv"
1 读入数据
类型：字符串
4.编写程序
a.append(item)
vip.
a[1]
a[0]
2 按VIP号排序
#冒泡排序
def bubble_sort(d):
for i in range(1,len(d)):
for j in range(1,len(d)-i):
d[j], d[j+1]=d[j+1],d[j]
int(d[j][0])>int(d[j+1][0]):
4.编写程序
if
j=m-1
else:
i=m+1
return -1 #未找到返回-1
if int(array[m][0])==s:
return m
if sj=len(array)-1 while i<=j:
m=(i+j)//2
3 按VIP号查找
#二分查找
):
bsearch(s,array
4.编写程序
i=1
def
key=int(input(‘请输入要查询的VIP号： ’)) m=bsearch(key,a)
if m!=-1:
print(a[m][1],"先生/女士, 您的积分为:",a[m][3]) else:
print("找不到VIP号对应的用户信息!")
解决问题的关键在于分析问题设计算法
#读入数据存入数组a中 #代码见P9
def bubble_sort(d):
#代码见P10
def bsearch(s,array):
#代码见P11
bubble_sort(a)
_______________
4 调用输出
4.编写程序
VIP号 姓名 飞行里程（km）
积分
600214 韩江辉 16801
519
601278 蒋志来 5321
78
600815 李亚东 28745
436
…… …… ……
……
603692 赵新星 5321
78
600087 蔡佳宁 112703
958
实例拓展 航空公司积分升级服 务
航空公司根据会员的积分推出升级服务，现
要对积分在[500,800]的会员进行升级，请编程找 出积分在此范围的所有会员。
查找积分在[500,800]的会员
二分查找
排序关键字： 积分
设计算法
排序
1.要进行几次二分查找？ 两次二 分查找
2.500(800)在积分中一定存在吗？ 可能不存在 >500
i m j
200370 430 560 585 610 790 820 932 968
0 1 2 3 4 5 6 7 8 9
查找积分在[500,800]的会员
设计算法
200370 430 560 585 610 790 820 932 968 i m j
200370 430 560 585 610 790 820 932 968
0 1 2 3 4 5 6 7 8 9
1.要进行几次二分查找？ 两次二 分查找
2.500(800)在积分中一定存在吗？ 可能不存在 >500
j im
查找积分在[500,800]的会员
0 1 2 3 4 5 6 7 8 9
设计算法
1.要进行几次二分查找？ 两次二 分查找
2.500(800)在积分中一定存在吗？ 可能不存在 >500
j i
200370 430 585 790 820 932 968
0 1 2 3 4 5 6 7 8 9
200370 430 585 790 820 932 968
0 1 2 3 4 5 6 7 8 9
j i
560
查找积分在[500,800]的会员
设计算法
610
610
560
m
1.要进行几次二分查找？ 两次二 分查找
2.500(800)在积分中一定存在吗？ 可能不存在 >500
3.500(800)的积分会不会存在多个？ 可能存在 找最左500和最右800 i m j
200470 500 500 500 500 500 650 730 968
0 1 2 3 4 5 6 7 8 9
查找积分在[500,800]的会员
设计算法
1.要进行几次二分查找？ 两次二分查找
2.500(800)在积分中一定存在吗？ 可能不存在 >500
200470 630 760 800 800 800 800 800 968
0 1 2 3 4 5 6 7 8 9
j im
可能存在 找最左500和最右800
3.500(800)的积分会不会存在多个？
200470 500 500 500 500 500 650 730 968
查找积分在[500,800]的会员
0 1 2 3 4 5 6 7 8 9
设计算法
m
i
j
1.要进行几次二分查找？ 两次二分查找
2.500(800)在积分中一定存在吗？ 可能不存在 >500
3.500(800)的积分会不会存在多个？ 可能存在 找最左500和最右800
j i
500
- oj i
200470 630 760 800 800 800 800 800 968
0 1 2 3 4 5 6 7 8 9
200470 500 500 500 650 730 968
查找积分在[500,800]的会员
0 1 2 3 4 5 6 7 8 9
设计算法
500
m
200470 500 500 500 500 500 650 730 968
200370 430 560 585 610 790 820 932 968
查找积分在[500,800]的会员
j位置数1.积分大于等于500
j i
设计算法
i
j
j位置数<=keyj i
200370 430 560 585 610 790 820 932 968
200470 630 760 800 800 800 800 800 968
查找积分在[500,800]的会员
2.积分小于等于800
设计算法
j
i
1 按积分排序
#冒泡排序
def bubble_sort1(d):
for i in range(1,len(d)):
for j in range(1,len(d)-i):
(d[j+1][0]):
int(d[j][0])>int
d[j], d[j+1]=d[j+1],d[j]
4.编写程序
if
1 按积分排序
#冒泡排序
def bubble_sort1(d):
for i in range(1,len(d)):
for j in range(1,len(d)-i):
(d[j+1][3]):
int(d[j][3])>int
d[j], d[j+1]=d[j+1],d[j]
4.编写程序
if
def bsearchz(s,array):
i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if int(array[m][0])==s:
return m
if sj=m-1
else:
i=m+1
return -1
200470 500 500 500 500 500 650 730 968
j位置数200370 430 560 585 610 790 820 932 968
2 按积分相等往左查找
j i
i
j
def bsearchz(s,array):
i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if sj=m-1
else:
i=m+1
return -1
200470 500 500 500 500 500 650 730 968
j位置数200370 430 560 585 610 790 820 932 968
2 按积分相等往左查找
j i
i
j
def bsearchz(s,array):
i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if sj=m-1
else:
i=m+1
return -1
200470 500 500 500 500 500 650 730 968
j位置数200370 430 560 585 610 790 820 932 968
2 按积分相等往左查找
j i
i
j
def bsearchz(s,array):
i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if s<=int(array[m][ 3]):
j=m-1
else:
i=m+1
return -1
200470 500 500 500 500 500 650 730 968
j位置数200370 430 560 585 610 790 820 932 968
2 按积分相等往左查找
j i
i
j
def bsearchz(s,array):
i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if s<=int(array[m][ 3]):
j=m-1
else:
i=m+1
return i
200470 500 500 500 500 500 650 730 968
j位置数200370 430 560 585 610 790 820 932 968
2 按积分相等往左查找
j i
i
j
def bsearchz(s,array):
i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if s<=int(array[m][3]):
j=m-1
else:
i=m+1
return □i
200470 500 500 500 500 500 650 730 968
j位置数200370 430 560 585 610 790 820 932 968
2 按积分相等往左查找
j i
i
j
def bsearchy(s,array): i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if s<=int(array[m][3]):
j=m-1
else:
i=m+1
return i
200470 630 760 800 800 800 800 800 968
j位置数<=key200370 430 560 585 610 790 820 932 968
3 按积分相等往右查找
j
j
i
i
def bsearchy(s,array): i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if sj=m-1
else:
i=m+1
return i
200470 630 760 800 800 800 800 800 968
j位置数<=key200370 430 560 585 610 790 820 932 968
3 按积分相等往右查找
j
j
i
i
def bsearchy(s,array): i=1
j=len(array)-1
while i<=j:
m=(i+j)//2
if sj=m-1
else:
i=m+1
return j
200470 630 760 800 800 800 800 800 968
j位置数<=key200370 430 560 585 610 790 820 932 968
3 按积分相等往右查找
j
j
i
i
bubble_sort1(a) #按积分排序
key1=int(input("请输入要查询的积分最小值:") key2=int(input("请输入要查询的积分最大值:")
p=bsearchz(key1,a)
q=bsearchy(key2,a)
print("积分在",key1,"至",key2,"的用户有:")
for i in range(p,q+1):
print(a[i][1])
3 主程序
#读入数据存入数组a中 #代码见P9
def bubble_sort(d):
#代码见P23
def bsearchz (s,array):
#代码见P25
def bsearchz (s,array):
#代码见P26 ★
迁移改变 归纳功能
关键要看清找到后继续往哪边查找
找到后继续往左边找 j位置数找到后继续往右边找 j位置数<=key算法思想关键点在于查找范围的不断缩小， 效率比较高，但要按查找关键字先排序
◆找到不退出
◆二分查找
课堂小结