《查找算法設計》教學課件2

4.3查找算法設計順序查找和對半查找查找是一種查詢數據的技術，其目標是能以比較少的步聚和較短的時間找到所需的對象。順序查找的基本思想是從第一個數據開始，按數據的順序逐個將數據與給定的值進行比較。若某個數據和給定的值相等，則查找成功，找到所查數據的位置；反之，查找不成功。查找算法順序查找27363218d(1)d(2)d(3)d(4)輸入查找的元素值key=32i=1i=2i=3此時d(i)=key,數組中的第3個位置從數組d的第1個元素d(1)開始，依次判斷各元素的值是否與查找鍵key的值相等。順序查找如果輸入查找的元素值key=22i=1i=2i=3i=4i=527363218d(1)d(2)d(3)d(4)此時i等于5,超過數組中元素個數,找不到從數組d的第1個元素d(1)開始，依次判斷各元素的值是否與查找鍵key的值相等。順序查找的流程圖開始i1d(i)=key?i<=n?ii+1未找到，輸出結果：0找到，輸出結果：i結束YNYN轉化成程序PrivateSubCommand6_Click()'順序查找Key=Val(Text2.Text)Fori=1TonumIfd(i)=KeyThenLabel5.Caption="在數組的"+Str(i)+"位置中"

ExitForEndIfNextIfi=num+1ThenLabel5.Caption="在數組中沒有找到"+Str(Key)EndIfEndSub對半查找的基本思想對半查找的前提是數據已經有序（以遞增為例），然后把待查找的數據與數組中間位置的數比較，如果比中間位置的數大，在數組的后半部分繼續查找，否則在數組的前半部分查找，繼續對分查找，直到找到待查找的數在數組中的位置或數組已無法對分。1015171822273545485265677285979812345678910111213141516下標元素數組d(i):I=1J=16M=fix((i+j)/2)=8第1次比較：Key>d(m)查找范圍應該變成d(9)~d(16)Key=52我們用變量I和J記錄所要查找范圍的起始和終止位置（1）過程：1015171822273545485265677285979812345678910111213141516下標元素數組d():I=9J=16M=fix((i+j)/2)=12第2次比較：Key<d(m)查找范圍應該變成d(9)~d(11)Key=52我們用變量I和J記錄所要查找范圍的起始和終止位置1015171822273545485265677285979812345678910111213141516下標元素I=9J=11M=fix((i+j)/2)=10第3次比較：Key=d(m)找到了Key=52在規模為n的數組變量d中進行對分查找的流程圖未找到，輸出結果：0開始I←1，j←ni<=j?找到，輸出結果：m結束NY計算中點m←(i+j)\2d(m)=key?D(m)<key?i←m+1j←m-1YYNN代碼分析command4的click過程Key=Val(Text2.Text)i=1j=numDoWhilei<=j

Ifd(M)=KeyThenLabel6.Caption="在數組的"+Str(M)+"位置中"

ExitSubEndIfIfd(M)<KeyThen

ElseEndIfLoopLabel6.Caption="在數組中沒有找到"+Str(Key)m=(i+j)\2i=m+1j=m-1比較順序查找是一種基本、簡單的查找算法，但查找的效率往往過低；對分查找時每次都把查