查找算法順序查找對(duì)分查找查找算法順序查找查找是一種查詢數(shù)據(jù)的技術(shù)，其目標(biāo)是能以比較少的步聚和較短的時(shí)間找到所需的對(duì)象。順序查找的基本思想

是從第一個(gè)數(shù)據(jù)開(kāi)始，按數(shù)據(jù)的順序逐個(gè)將數(shù)據(jù)與給定的值進(jìn)行比較。若某個(gè)數(shù)據(jù)和給定的值相等，則查找成功，找到所查數(shù)據(jù)的位置；反之，查找不成功。查找算法查找是一種查詢數(shù)據(jù)的技術(shù)，其目標(biāo)是能以比較少的步聚和較短的時(shí)順序查找27363218d(1)d(2)d(3)d(4)輸入查找的元素值key=32i=1i=2i=3此時(shí)d(i)=key,數(shù)組中的第3個(gè)位置如果輸入查找的元素值key=22i=1i=2i=3i=4i=527363218d(1)d(2)d(3)d(4)此時(shí)i等于5,超過(guò)數(shù)組中元素個(gè)數(shù),找不到從數(shù)組d的第1個(gè)元素d(1)開(kāi)始，依次判斷各元素的值是否與查找鍵key的值相等。順序查找27363218d(1)d(2)d(3)順序查找的流程圖開(kāi)始i1d(i)=key?i<=n?ii+1未找到，輸出結(jié)果：0找到，輸出結(jié)果：i結(jié)束YNYN順序查找的流程圖開(kāi)始i1d(i)=key?i<=轉(zhuǎn)化成程序Key=Val(Text1.Text)Fori=1TonIfd(i)=KeyThenLabel1.Caption="在數(shù)組的"+Str(i)+"位置中"ExitForEndIfNextiIfi=n+1ThenLabel1.Caption="在數(shù)組中沒(méi)有找到"+Str(Key)EndIf轉(zhuǎn)化成程序Key=Val(Text1.Text)1、從數(shù)組的第1個(gè)元素開(kāi)始，不斷判斷d(i)是否等于key2、最少查找1次，最多查找n次3、查找成功，輸出該元素的下標(biāo)i

查找不成功，輸出“未找到”在d(n)中用順序查找方法查找某個(gè)值的規(guī)律：1、從數(shù)組的第1個(gè)元素開(kāi)始，不斷判斷d(i)是否等于key思考1：

如何在最短時(shí)間猜中1000以內(nèi)數(shù)字？每次猜中間數(shù)字！思考1：每次猜中間數(shù)字！對(duì)分查找的基本思想對(duì)分查找的前提是數(shù)據(jù)已經(jīng)有序（以遞增為例），然后把待查找的數(shù)據(jù)與數(shù)組中間位置的數(shù)比較，如果比中間位置的數(shù)大，在數(shù)組的后半部分繼續(xù)查找，否則在數(shù)組的前半部分查找，繼續(xù)對(duì)分查找，直到找到待查找的數(shù)在數(shù)組中的位置或數(shù)組已無(wú)法對(duì)分。對(duì)分查找算法對(duì)分查找的基本思想對(duì)分查找算法12345678910111213141516下標(biāo)元素M=fix((i+j)/2)=8I=1J=16第1次比較：Key>d(m)查找范圍應(yīng)該變成d(9)~d(16)Key=52①變量I和J記錄所要查找范圍的起始和終止位置過(guò)程：12345678910111213141516下標(biāo)元素J=16M=fix((i+j)/2)=12第2次比較：Key<d(m)查找范圍應(yīng)該變成d(9)~d(11)12345678910111213141516下標(biāo)元素I=9J=11M=fix((i+j)/2)=10第3次比較：Key=d(m)找到了！②計(jì)算中間點(diǎn)M的位置：M=fix((i+j)/2)或M=(i+j)\2③比較key和d(M)的值，根據(jù)結(jié)果重新確定查找的起始和終止位置或者直接告訴已經(jīng)找到J不變，I=M+1=9I=9I不變，J=M-1=1112345678910111213141516下標(biāo)元素M=f在規(guī)模為n的數(shù)組變量d中進(jìn)行對(duì)分查找的流程圖未找到，Print0開(kāi)始I←1，j←ni<=j?找到，Printm結(jié)束NY計(jì)算中點(diǎn)m←fix((i+j)/2)d(m)=key?key<d(m)?j←m-1i←m+1YYNN81在規(guī)模為n的數(shù)組變量d中進(jìn)行對(duì)分查找的流程圖未找到，Prii=1：j=nDoWhilei<=j

m=fix((i+j)/2)’或m=(i+j)\2Ifd(m)<>KeyThenIfKey<d(m)Then

j=m-1Elsei=m+1EndIfelsePrintmExitDoEndIfLoopIfi>jThenPrint“0”轉(zhuǎn)

化

成

程

序i=1：j=n轉(zhuǎn)

化

成

程

序練習(xí)題1、數(shù)據(jù)320,340,347,349,362,382,423,454，使用對(duì)分查找，設(shè)定查找鍵key，若第一個(gè)被訪問(wèn)到的數(shù)據(jù)是349，小于key值，則第二個(gè)被訪問(wèn)到的數(shù)據(jù)是（）A.340B.382C.423D.4542、7位學(xué)員的身高(單位:cm)從高到低依次為：178,177,175,172,170,165,162，用對(duì)分查找法找到178的過(guò)程中，依次被訪問(wèn)到的數(shù)據(jù)是（）A.178B.172,175,178C.172,177,178D.172,175,177,178練習(xí)題1、數(shù)據(jù)320,340,347,349,362,382比較順序查找是一種基本、簡(jiǎn)單的查找算法，但查找的效率往往過(guò)低；對(duì)分查找時(shí)每次都把查找范圍縮小一半對(duì)分查找算法數(shù)據(jù)次數(shù)較少，效率較高，但它要求數(shù)組中的數(shù)據(jù)是有序的。比較順序查找是一種基本、簡(jiǎn)單的查找算法，但查找的效率往往過(guò)低順序查找與對(duì)分查找比較順序查找與對(duì)分查找比較查找算法順序查找對(duì)分查找查找算法順序查找查找是一種查詢數(shù)據(jù)的技術(shù)，其目標(biāo)是能以比較少的步聚和較短的時(shí)間找到所需的對(duì)象。順序查找的基本思想

是從第一個(gè)數(shù)據(jù)開(kāi)始，按數(shù)據(jù)的順序逐個(gè)將數(shù)據(jù)與給定的值進(jìn)行比較。若某個(gè)數(shù)據(jù)和給定的值相等，則查找成功，找到所查數(shù)據(jù)的位置；反之，查找不成功。查找算法查找是一種查詢數(shù)據(jù)的技術(shù)，其目標(biāo)是能以比較少的步聚和較短的時(shí)順序查找27363218d(1)d(2)d(3)d(4)輸入查找的元素值key=32i=1i=2i=3此時(shí)d(i)=key,數(shù)組中的第3個(gè)位置如果輸入查找的元素值key=22i=1i=2i=3i=4i=527363218d(1)d(2)d(3)d(4)此時(shí)i等于5,超過(guò)數(shù)組中元素個(gè)數(shù),找不到從數(shù)組d的第1個(gè)元素d(1)開(kāi)始，依次判斷各元素的值是否與查找鍵key的值相等。順序查找27363218d(1)d(2)d(3)順序查找的流程圖開(kāi)始i1d(i)=key?i<=n?ii+1未找到，輸出結(jié)果：0找到，輸出結(jié)果：i結(jié)束YNYN順序查找的流程圖開(kāi)始i1d(i)=key?i<=轉(zhuǎn)化成程序Key=Val(Text1.Text)Fori=1TonIfd(i)=KeyThenLabel1.Caption="在數(shù)組的"+Str(i)+"位置中"ExitForEndIfNextiIfi=n+1ThenLabel1.Caption="在數(shù)組中沒(méi)有找到"+Str(Key)EndIf轉(zhuǎn)化成程序Key=Val(Text1.Text)1、從數(shù)組的第1個(gè)元素開(kāi)始，不斷判斷d(i)是否等于key2、最少查找1次，最多查找n次3、查找成功，輸出該元素的下標(biāo)i

查找不成功，輸出“未找到”在d(n)中用順序查找方法查找某個(gè)值的規(guī)律：1、從數(shù)組的第1個(gè)元素開(kāi)始，不斷判斷d(i)是否等于key思考1：

如何在最短時(shí)間猜中1000以內(nèi)數(shù)字？每次猜中間數(shù)字！思考1：每次猜中間數(shù)字！對(duì)分查找的基本思想對(duì)分查找的前提是數(shù)據(jù)已經(jīng)有序（以遞增為例），然后把待查找的數(shù)據(jù)與數(shù)組中間位置的數(shù)比較，如果比中間位置的數(shù)大，在數(shù)組的后半部分繼續(xù)查找，否則在數(shù)組的前半部分查找，繼續(xù)對(duì)分查找，直到找到待查找的數(shù)在數(shù)組中的位置或數(shù)組已無(wú)法對(duì)分。對(duì)分查找算法對(duì)分查找的基本思想對(duì)分查找算法12345678910111213141516下標(biāo)元素M=fix((i+j)/2)=8I=1J=16第1次比較：Key>d(m)查找范圍應(yīng)該變成d(9)~d(16)Key=52①變量I和J記錄所要查找范圍的起始和終止位置過(guò)程：12345678910111213141516下標(biāo)元素J=16M=fix((i+j)/2)=12第2次比較：Key<d(m)查找范圍應(yīng)該變成d(9)~d(11)12345678910111213141516下標(biāo)元素I=9J=11M=fix((i+j)/2)=10第3次比較：Key=d(m)找到了！②計(jì)算中間點(diǎn)M的位置：M=fix((i+j)/2)或M=(i+j)\2③比較key和d(M)的值，根據(jù)結(jié)果重新確定查找的起始和終止位置或者直接告訴已經(jīng)找到J不變，I=M+1=9I=9I不變，J=M-1=1112345678910111213141516下標(biāo)元素M=f在規(guī)模為n的數(shù)組變量d中進(jìn)行對(duì)分查找的流程圖未找到，Print0開(kāi)始I←1，j←ni<=j?找到，Printm結(jié)束NY計(jì)算中點(diǎn)m←fix((i+j)/2)d(m)=key?key<d(m)?j←m-1i←m+1YYNN81在規(guī)模為n的數(shù)組變量d中進(jìn)行對(duì)分查找的流程圖未找到，Prii=1：j=nDoWhilei<=j

m=fix((i+j)/2)’或m=(i+j)\2Ifd(m)<>KeyThenIfKey<d(m)Then

j=m-1Elsei=m+1EndIfelsePrintmExitDoEndIfLoopIfi>jThenPrint“0”轉(zhuǎn)

化

成

程

序i=1：j=n轉(zhuǎn)

化

成

程

序練習(xí)題1、數(shù)據(jù)320,340,347,349,362,382,423,454，使用對(duì)分查找，設(shè)定查找鍵key，若第一個(gè)被訪問(wèn)到的數(shù)據(jù)是349，小于key值，則第二個(gè)被訪問(wèn)到的數(shù)據(jù)是（）A.340B.382C.423D.4542、7位學(xué)員的身高(單位:cm)從高到低依次為：178,177,175,172,170,165,162，用對(duì)分查找法找到178