5.4.3查找算法的應用實例分析航空公司VIP會員積分查詢不少航空公司都會提供優惠的會員服務，當某會員飛行里程累積達到一定數量后，可以使用里程積分兌換獎勵機票或獎勵升艙等服務。現給定某航空公司部分VIP會員的飛行里程、積分等信息，如下表所示，要求實現根據VIP號碼快速查詢會員積分的功能。VIP號姓名飛行里程（km）積分600214韓江輝16801519601278蔣志來532178600815李亞東28745436607854王慶生186139605719李燕7493138603532王曉燕6875102600101鄭煜明14253236（1）抽象與建模從表中的數據可以看出，每個會員的信息是一條記錄，包括VIP號、姓名、飛行里程、積分等數據項。要顯示某個會員的積分信息，先得從多條記錄中查找到該會員的記錄，如下所示：×××××××××××××××××若用a[i]表示該條記錄，則該會員的積分可采用以下形式表示：a[i][3](表示該條記錄的第4個數據項的值)（2）設計算法與數據結構對表格數據可采用4個一維數組按列或1個一維數組按行來存儲。要顯示某個會員的積分，先要從多條會員信息的數據中找到該會員。查找可采用順序查找算法或二分查找算法。從算法的時間復雜度方面考慮，二分查找算法的效率高于順序查找算法，但若采用二分查找算法，被查找的數據序列必須是有序的，即要按VIP號為關鍵字進行排序。（3）編寫程序假如數據以1個一維數組按行來存儲，利用二分查找算法查找，程序如下：importcsv#數據讀入csvFile=open(“vip.csv”,”r”)reader=csv.reader(csvFile)a=[]foriteminreader:a.append(item)csvFile.close()#排序defbubble_sort(d):foriinrange(1,len(d)):forjinrange(1,len(d)-i):ifint(d[j][0])>int(d[j+1][0]):temp=d[j]d[j]=d[j+1]d[j+1]=temp#二分查找defbsearch(s,array):i=1j=len(array)-1whilei<=j:m=(i+j)//2ifint(array[m][0])==s:returnmifs<int(array[m][0]):j=m-1else:i=m+1return-1#未找到返回-1bubble_sort(a)key=int(input(‘請輸入要查詢的VIP號：’))m=bsearch(key,a)ifm!=-1:print(a[m][1],”先生/女士，您的積分為：”,a[m][3])else:print(‘找不到VIP號對應的用戶信息！’)當輸入VIP編號“600815”時，程序輸出“李亞東先生/女士，您的積分為：436”的信息。若將上例中的二分查找改成順序查找，代碼可寫成如下形式：importcsv#數據讀入csvFile=open(“vip.csv”,”r”)reader=csv.reader(csvFile)a=[]foriteminreader:a.append(item)csvFile.close()defseq_search(item,a):length=len(a)flag=Falseforiinrange(1,length+1):#查找范圍不包含第一行數據ifa[i][0]==item:flag=Truebreakifflag==True:returni

else:return-1key=int(input(‘請輸入要查詢的VIP號：’))m=bsearch(key,a)ifm!=-1:print(a[m][1],“先生/女士，您的積分為：”,a[m][3])else:print(‘找不到VIP號對應的用戶信息！’)

練習用二分查找實現開平方根函數squareroot(x,p)。x是被開方的數，假定輸入的數都為非負整數，p是誤差上限，輸出一個浮點數結果。defsquare(x,p):ifx<0:return-1a=0b=xwhilea<=b:m=(a+b)/2ifabs(m**2-x)<p:returnmelifm**2>x:b=m

else:a=mprint(square(2,0.01))print(square(1,0.01))print(square(9,0.01)