5.4.1順序查找課件-浙教版高中信息技術選修1

5.4.1順序查找查找又稱檢索，計算機根據(jù)所給條件查找出滿足條件的對象，即在存儲的一批數(shù)據(jù)內尋找出一個特定的數(shù)據(jù)，或者確定在該批數(shù)據(jù)內是否存在這樣的數(shù)據(jù)。若沒有找到滿足條件的對象，則返回特定值，表明查找失敗；若查找到滿足條件的對象，則表明查找成功，一般要求返回該對象的存儲位置或對象值本身。通常，程序將按照查找的結果（找到或未找到）來決定接著應執(zhí)行后面哪一個計算步驟。順序查找順序查找又稱線性查找，從順序表的一端開始，依次將每個元素的關鍵字與給定值key（查找鍵）進行比較。若某個元素的關鍵字等于key，則表明查找成功；若所有元素都比較完畢仍找不到，則表明查找失敗。如下圖所示，在規(guī)模為8的數(shù)組d中，分別按順序查找算法尋找數(shù)據(jù)18和15的情況，處理過程中找到的第4個數(shù)組元素d[3]中的數(shù)據(jù)與18相等，表示8個數(shù)據(jù)中存在值為18的元素；而若key為15時，查找完所有數(shù)據(jù)仍未找到，表示8個數(shù)據(jù)中不存在值為15的元素。18keyd252213181411171901234567到此處已找到15keyd252213181411171901234567查完所有數(shù)據(jù)仍未找到順序查找過程實例時間復雜度為O(n)開始i0i≤n-1?d[i]=key?ii+1是否找到，輸出信息未找到，輸出信息結束順序查找算法流程圖是否實現(xiàn)此算法的Python程序如下：d=[25,22,13,18,14,11,17,19]key=18flag=Falselength=len(d)foriinrange(length):ifd[i]==key:flag=Truebreakifflag=True:print(“查找成功！”)else:print(“未找到”)順序查找算法也可以寫成函數(shù)的形式，如下所示：defseq_search(s,a):length=len(s)flag=Falseforiinrange(length):ifs[i]==a:flag=Truebreakifflag==True:returnielse:returnFalsed=[25,22,13,18,14,11,17,19]key=15result=seq_search(d,key)print(result)小結順序查找本質上是一種枚舉算法思想，順序查找程序就是用循環(huán)來枚舉所有要查找的對象，然后在循環(huán)體內用條件判斷當前枚舉出的對象是否等于查找對象。假設n個數(shù)據(jù)依次存儲在長度為n的數(shù)組a中，查找鍵為key，自定義函數(shù)seq_search(a,key)返回數(shù)組a中首個值為key的元素下標，若找不到key則返回-1。defseq_search(a,key):foriinrange(len(a)):ifa[i]==key:returnielse:return-1練一練1.某個列表中共有m個元素，進行順序查找之后查找失敗，則其中元素的比較次數(shù)是（）A.mB.m2C.m-1D.(m+1)//2A2.有如下python程序段：a=[2,6,8,8,2,4,7,3]p=0foriinrange(1,len(a)):ifa[i]>a[p]:p=i則運行該段代碼后，變量p的值為（）A.0B.2C.3D.8B3.有如下Python程序段：key=int(input(“key=”))s=0a=[]foriinrange(10):a.append(i+1)foriinrange(len(a)):ifa[i]%key==0:s=s+1print(s)當輸入的key=5時，程序運行結束后，輸出的值為（）A.0B.1C.2D.3C4.查找一個英文句子中是否包含某個單詞，可以使用順序查找的方法，實現(xiàn)上述功能的Python程序段如下，請在劃線處填入合適的代碼。long=“Ihaveanappleandanorange.”word=input(“輸入要查找的單詞：”)flag=____________________________foriinrange(len(long)-len(word)):iflong[______________]==word:print(“yes”)