1、5.4.3 查找算法的应用实例分析航空公司VIP会员积分查询不少航空公司都会提供优惠的会员服务，当某会员飞行里程累积达到一定数量后，可以使用里程积分兑换奖励机票或奖励升舱等服务。现给定某航空公司部分VIP会员的飞行里程、积分等信息，如下表所示，要求实现根据VIP号码快速查询会员积分的功能。VIPVIP号号姓名姓名飞行里程（飞行里程（kmkm）积分积分600214韩江辉16801519601278蒋志来532178600815李亚东28745436607854王庆生186139605719李燕7493138603532王晓燕6875102600101郑煜明14253236（1）抽象与建模从表中的
2、数据可以看出，每个会员的信息是一条记录，包括VIP号、姓名、飞行里程、积分等数据项。要显示某个会员的积分信息，先得从多条记录中查找到该会员的记录，如下所示：若用ai表示该条记录，则该会员的积分可采用以下形式表示：ai3(表示该条记录的第4个数据项的值)（2）设计算法与数据结构对表格数据可采用4个一维数组按列或1个一维数组按行来存储。要显示某个会员的积分，先要从多条会员信息的数据中找到该会员。查找可采用顺序查找算法或二分查找算法。从算法的时间复杂度方面考虑，二分查找算法的效率高于顺序查找算法，但若采用二分查找算法，被查找的数据序列必须是有序的，即要按VIP号为关键字进行排序。（3）编写程序假如数
3、据以1个一维数组按行来存储，利用二分查找算法查找，程序如下：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(dj0)int(dj+10):temp=dj dj=dj+1 dj+1=temp#二分查找def bsearch(s,array):i=1 j=
4、len(array)-1 while i=j:m=(i+j)/2 if int(arraym0)=s:return m if sint(arraym0):j=m-1 else:i=m+1 return-1#未找到返回-1bubble_sort(a)key=int(input(请输入要查询的VIP号：)m=bsearch(key,a)if m!=-1:print(am1,”先生/女士，您的积分为：”,am3)else:print(找不到VIP号对应的用户信息！)当输入VIP编号“600815”时，程序输出“李亚东 先生/女士，您的积分为：436”的信息。若将上例中的二分查找改成顺序查找，代码可写
5、成如下形式：import csv#数据读入csvFile=open(“vip.csv”,”r”)reader=csv.reader(csvFile)a=for item in reader:a.append(item)csvFile.close()def seq_search(item,a):length=len(a)flag=False for i in range(1,length+1):#查找范围不包含第一行数据 if ai0=item:flag=True break if flag=True:return i else:return -1key=int(input(请输入要查询的VIP
6、号：)m=bsearch(key,a)if m!=-1:print(am1,“先生/女士，您的积分为：”,am3)else:print(找不到VIP号对应的用户信息！)练 习用二分查找实现开平方根函数squareroot(x,p)。x是被开方的数，假定输入的数都为非负整数，p是误差上限，输出一个浮点数结果。def square(x,p):if x0:return-1 a=0 b=x while a=b:m=(a+b)/2 if abs(m*2-x)x:b=m else:a=mprint(square(2,0.01)print(square(1,0.01)print(square(9,0.01)print(square(100,0.01)测试结果：1.4140625 0.99609375 3.00146484375 9.999847412109375谢 谢
