(
课件网) 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 s
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 5 ... ... 
