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

5.4.1順序查找查找又稱檢索，計(jì)算機(jī)根據(jù)所給條件查找出滿足條件的對(duì)象，即在存儲(chǔ)的一批數(shù)據(jù)內(nèi)尋找出一個(gè)特定的數(shù)據(jù)，或者確定在該批數(shù)據(jù)內(nèi)是否存在這樣的數(shù)據(jù)。若沒(méi)有找到滿足條件的對(duì)象，則返回特定值，表明查找失??；若查找到滿足條件的對(duì)象，則表明查找成功，一般要求返回該對(duì)象的存儲(chǔ)位置或?qū)ο笾当旧?。通常，程序?qū)凑詹檎业慕Y(jié)果（找到或未找到）來(lái)決定接著應(yīng)執(zhí)行后面哪一個(gè)計(jì)算步驟。順序查找順序查找又稱線性查找，從順序表的一端開(kāi)始，依次將每個(gè)元素的關(guān)鍵字與給定值key（查找鍵）進(jìn)行比較。若某個(gè)元素的關(guān)鍵字等于key，則表明查找成功；若所有元素都比較完畢仍找不到，則表明查找失敗。如下圖所示，在規(guī)模為8的數(shù)組d中，分別按順序查找算法尋找數(shù)據(jù)18和15的情況，處理過(guò)程中找到的第4個(gè)數(shù)組元素d[3]中的數(shù)據(jù)與18相等，表示8個(gè)數(shù)據(jù)中存在值為18的元素；而若key為15時(shí)，查找完所有數(shù)據(jù)仍未找到，表示8個(gè)數(shù)據(jù)中不存在值為15的元素。18keyd252213181411171901234567到此處已找到15keyd252213181411171901234567查完所有數(shù)據(jù)仍未找到順序查找過(guò)程實(shí)例時(shí)間復(fù)雜度為O(n)開(kāi)始i0i≤n-1?d[i]=key?ii+1是否找到，輸出信息未找到，輸出信息結(jié)束順序查找算法流程圖是否實(shí)現(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(“未找到”)順序查找算法也可以寫(xiě)成函數(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)小結(jié)順序查找本質(zhì)上是一種枚舉算法思想，順序查找程序就是用循環(huán)來(lái)枚舉所有要查找的對(duì)象，然后在循環(huán)體內(nèi)用條件判斷當(dāng)前枚舉出的對(duì)象是否等于查找對(duì)象。假設(shè)n個(gè)數(shù)據(jù)依次存儲(chǔ)在長(zhǎng)度為n的數(shù)組a中，查找鍵為key，自定義函數(shù)seq_search(a,key)返回?cái)?shù)組a中首個(gè)值為key的元素下標(biāo)，若找不到key則返回-1。defseq_search(a,key):foriinrange(len(a)):ifa[i]==key:returnielse:return-1練一練1.某個(gè)列表中共有m個(gè)元素，進(jìn)行順序查找之后查找失敗，則其中元素的比較次數(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則運(yùn)行該段代碼后，變量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)當(dāng)輸入的key=5時(shí)，程序運(yùn)行結(jié)束后，輸出的值為（）A.0B.1C.2D.3C4.查找一個(gè)英文句子中是否包含某個(gè)單詞，可以使用順序查找的方法，實(shí)現(xiàn)上述功能的Python程序段如下，請(qǐng)?jiān)趧澗€處填入合適的代碼。long=“Ihaveanappleandanorange.”word=input(“輸入要查找的單詞：”)flag=____________________________foriinrange(len(long)-len(word)):iflong[______________]==word:print(“yes”)