查找算法設(shè)計查找算法設(shè)計1隨機產(chǎn)生若干個整數(shù)，使用順序查找和對分查找進行查尋數(shù)據(jù)，輸出查找結(jié)果。

隨機產(chǎn)生若干個整數(shù)，使用順序查找和對2新課引入

在到學習、工作和生活中我們經(jīng)常需要在一系列數(shù)據(jù)中查找出是否有某個特定數(shù)據(jù)，如在圖書館按書目查找某本書，在運動會上查尋某運動員的比賽成績，在網(wǎng)上搜索信息、使用QQ查找好友等，這時就會用到查找算法了。

新課引入在到學習、工作和生活中我們經(jīng)常需要在3問題提出

一、采用何種方法進行查找？

1.順序查找

順序查找是最容易想到，也是最容易實現(xiàn)的一種查找算法，方法是將要找的數(shù)據(jù)與數(shù)組中的每個數(shù)據(jù)從第一個開始逐一進行比較，直到找到或者全部找完。

問題提出一、采用何種方法進行查找？

1.順序查找

順序查找4（1）順序查找算法流程圖（1）順序查找算法流程圖5PrivateSubCommand6_Click()'順序查找

DimiAsInteger,keyAsInteger

key=Val(Text2.Text)'查找的數(shù)據(jù)

Fori=1Tonum'依次查找

Ifd(i)=keyThen'找到了數(shù)據(jù)

Label5.Caption="在數(shù)組的第"+Str(i)+"個位置"

ExitFor'中斷當前For循環(huán)

EndIf

Next

Ifi=num+1ThenLabel5.Caption="在數(shù)組中沒有找到數(shù)據(jù)"+Str(key)

EndSub

（2）編寫程序代碼PrivateSubCommand6_Click()6二、如果數(shù)組中有n個元素，那么順序查找的平均查找次數(shù)是（n+1）/2次，有沒有效率更高的查找算法呢？

1.猜數(shù)游戲

二、如果數(shù)組中有n個元素，那么順序查找的平均查找次數(shù)是（7

在猜數(shù)游戲過程，如何使用更少的次數(shù)猜對數(shù)字呢？采用對半策略。第一次猜50，結(jié)果是太小了，所以數(shù)字肯定在51～100，第二次就猜51～100的當中位置（取下限的整數(shù)），猜75，結(jié)果是太大了，所以數(shù)字肯定在51～74，再猜當中位置57，正好猜中！這種猜數(shù)的方法就是對分查找的算法。在猜數(shù)游戲過程，如何使用更少的次數(shù)猜對數(shù)82.對分查找算法首先將查找鍵與有序數(shù)組內(nèi)處于中間位置的元素進行比較，如果中間位置上的元素內(nèi)的數(shù)值與查找鍵不同，根據(jù)數(shù)組元素的有序性，就可確定應該在數(shù)組的前半部分還是后半部分繼續(xù)進行查找；在新確定的范圍內(nèi)，繼續(xù)按上述方法進行查找，直到獲得最終結(jié)果。對分查找的前提條件數(shù)組中的數(shù)據(jù)是已經(jīng)排序的。2.對分查找算法9(1)對分查找算法流程圖(1)對分查找算法流程圖10對分查找過程如下圖所示：對分查找過程如下圖所示：11（2）編寫程序代碼PrivateSubCommand4_Click()'對分查找

DimiAsInteger,jAsInteger,keyAsInteger,mAsInteger

DimncAsInteger

IfNotsortedThen'進行對分查找時，需先對數(shù)據(jù)進行排序

MsgBox"進行對分查找時，需先對數(shù)據(jù)進行排序"

ExitSub'結(jié)束過程

EndIf

key=Val(Text2.Text)'輸入查找的數(shù)據(jù)

i=1

j=num

nc=0'查找次數(shù)nc

DoWhilei<=j'對分查找

nc=nc+1

m=Fix((i+j)/2)

Ifd(m)=keyThen‘找到了

Label6.Caption="在數(shù)組的第"+Str(m)+"個位置，共查找了"+Str(nc)+"次"

ExitSub

EndIf

Ifkey<d(m)Then'未找到，繼續(xù)查找

j=m-1

Else

i=m+1

EndIf

Loop

Label6.Caption="在數(shù)組中沒有找到數(shù)據(jù)"+Str(key)+"，共查找了"+Str(nc)+"次"

EndSub

（2）編寫程序代碼PrivateSubCom12

使用對分查找，每次都把規(guī)模縮小一半，效率比順序查找要高，但在進行對分查找前，需要將它排好序。

（3）運行調(diào)試程序

根據(jù)算法流程圖,填空完善已經(jīng)設(shè)計好的界面和部分代碼的順序查找和對分查找算法，并進行調(diào)試。使用對分查找，每次都把規(guī)模縮小一半，效率比順13課堂練習1.一個數(shù)組中含有元素A、B、C、D、E、F、G、H、I、J、K、L、M、N應用對分查找算法，查找目標為J時，會查經(jīng)哪幾個字母，如果查找的是Z呢？參考答案：

使用對分查找，查找目錄J時，會查經(jīng)H、L，查找Z，會查經(jīng)H、L、N，最后查找z未找到。

課堂練習1.一個數(shù)組中含有元素A、B、C、D、E、F、G、H142.數(shù)組元素為：Alice、Byron、Duane、Elaine、Floyd、Gene、Herry、Iris，請回答：

①哪個查找算法（順序查找和對分查找）能比較快找到名字Gene?

②哪個查找算法（順序查找和對分查找）能比較快找到名字Alice?

③哪個查找算法（順序查找和對分查找）能比較快地測定名字Bruce不存在?

④哪個查找算法（順序查找和對分查找）能比較快地測定名字Sue不存在?

⑤當利用順序查找算法查找名字Floyd時，查問了多少個數(shù)據(jù)？使用對分查找算法時，又要查問多少個數(shù)據(jù)？

2.數(shù)組元素為：Alice、Byron、Duane、Elai15參考答案：①查找Gene：對分查找快，對分查找3次，順序查找6次②查找Alice：順序查找快，順序查找1次，對分查找4次③查找Bruce：對分查找快，對分查找4次，順序查找8次④查找Sue：對分查找快，對分查找4次，順序查找8次⑤使用順序查找Floyd，查找了5個數(shù)據(jù)，使用對分查找，查問了1個數(shù)據(jù)

參考答案：①查找Gene：對分查找快，對分查找3次，順序查找163.對于有5000個元素的數(shù)組，使用對分查找，最多查問多少個數(shù)據(jù)？使用順序查找呢？試比較兩種查找算法的效率。

參考答案：

使用對分查找最多查問log25001個數(shù)據(jù)，使用順序查找最多查問5000次，所以對分查找效率比較高。

3.對于有5000個元素的數(shù)組，使用對分查找，最多查問多少個174.驗血問題的算法。有１０萬大軍三天后將要出發(fā)作戰(zhàn)。軍醫(yī)發(fā)現(xiàn)有一位士兵帶入了一種傳染病菌，三天后發(fā)作將傳染給全軍，使部隊喪失作戰(zhàn)能力，只有通過驗血才能發(fā)現(xiàn)誰是患者。但當時軍醫(yī)每天至多只能檢驗１００份血樣，如果逐一地進行化驗需要１０００天，這將貽誤戰(zhàn)機。要求設(shè)計一個算法，幫助軍醫(yī)解決上述問題。4.驗血問題的算法。有１０萬大軍三天后將要出發(fā)作戰(zhàn)。軍醫(yī)發(fā)現(xiàn)18參考答案：

第一天，將10萬人分成100組，每組1000人，滴血于一處，成為一份血樣，總共有100份血樣，對這100份血樣進行驗血，查出帶菌血樣所在組A；第二天，將有帶菌血樣所在組A的1000人分成100組，每組10人，滴血于一處，成為一份血樣，總共有100份血樣，對這100份血樣進行驗血，查出帶菌血樣所在組B；第三天，將有帶菌血樣所在組B的10人分成10組，每組1人，滴血于一處，成為一份血樣，總共有10份血樣，對這10份血樣進行驗血，查出帶菌血樣所在組C，即找到帶有傳染病毒的士兵；

參考答案：19進行對分查找算法的前提是:(A)被查找數(shù)據(jù)元素個數(shù)是奇數(shù)

(B)被查找數(shù)據(jù)元素個數(shù)是偶數(shù)

(C)被查找數(shù)據(jù)元素是有序的

(D)被查找數(shù)據(jù)元素是無序的

參考答案：C進行對分查找算法的前提是:206.用對分查找法從數(shù)列3，6，7，10，12，16，25，30，75中找到數(shù)據(jù)10的最少查找次數(shù)是:(A)2(B)3(C)4(D)7

參考答案：B6.用對分查找法從數(shù)列3，6，7，10，12，16，25217.應用對分查找算法查找一個有200個表項的列表時，必須查問的表項數(shù)目至多有幾個？如果列表中有10萬個表項又怎樣？參考答案：8個，17個

7.應用對分查找算法查找一個有200個表項的列表時，22謝謝！謝謝！23查找算法設(shè)計查找算法設(shè)計24隨機產(chǎn)生若干個整數(shù)，使用順序查找和對分查找進行查尋數(shù)據(jù)，輸出查找結(jié)果。

隨機產(chǎn)生若干個整數(shù)，使用順序查找和對25新課引入

在到學習、工作和生活中我們經(jīng)常需要在一系列數(shù)據(jù)中查找出是否有某個特定數(shù)據(jù)，如在圖書館按書目查找某本書，在運動會上查尋某運動員的比賽成績，在網(wǎng)上搜索信息、使用QQ查找好友等，這時就會用到查找算法了。

新課引入在到學習、工作和生活中我們經(jīng)常需要在26問題提出

一、采用何種方法進行查找？

1.順序查找

順序查找是最容易想到，也是最容易實現(xiàn)的一種查找算法，方法是將要找的數(shù)據(jù)與數(shù)組中的每個數(shù)據(jù)從第一個開始逐一進行比較，直到找到或者全部找完。

問題提出一、采用何種方法進行查找？

1.順序查找

順序查找27（1）順序查找算法流程圖（1）順序查找算法流程圖28PrivateSubCommand6_Click()'順序查找

DimiAsInteger,keyAsInteger

key=Val(Text2.Text)'查找的數(shù)據(jù)

Fori=1Tonum'依次查找

Ifd(i)=keyThen'找到了數(shù)據(jù)

Label5.Caption="在數(shù)組的第"+Str(i)+"個位置"

ExitFor'中斷當前For循環(huán)

EndIf

Next

Ifi=num+1ThenLabel5.Caption="在數(shù)組中沒有找到數(shù)據(jù)"+Str(key)

EndSub

（2）編寫程序代碼PrivateSubCommand6_Click()29二、如果數(shù)組中有n個元素，那么順序查找的平均查找次數(shù)是（n+1）/2次，有沒有效率更高的查找算法呢？

1.猜數(shù)游戲

二、如果數(shù)組中有n個元素，那么順序查找的平均查找次數(shù)是（30

在猜數(shù)游戲過程，如何使用更少的次數(shù)猜對數(shù)字呢？采用對半策略。第一次猜50，結(jié)果是太小了，所以數(shù)字肯定在51～100，第二次就猜51～100的當中位置（取下限的整數(shù)），猜75，結(jié)果是太大了，所以數(shù)字肯定在51～74，再猜當中位置57，正好猜中！這種猜數(shù)的方法就是對分查找的算法。在猜數(shù)游戲過程，如何使用更少的次數(shù)猜對數(shù)312.對分查找算法首先將查找鍵與有序數(shù)組內(nèi)處于中間位置的元素進行比較，如果中間位置上的元素內(nèi)的數(shù)值與查找鍵不同，根據(jù)數(shù)組元素的有序性，就可確定應該在數(shù)組的前半部分還是后半部分繼續(xù)進行查找；在新確定的范圍內(nèi)，繼續(xù)按上述方法進行查找，直到獲得最終結(jié)果。對分查找的前提條件數(shù)組中的數(shù)據(jù)是已經(jīng)排序的。2.對分查找算法32(1)對分查找算法流程圖(1)對分查找算法流程圖33對分查找過程如下圖所示：對分查找過程如下圖所示：34（2）編寫程序代碼PrivateSubCommand4_Click()'對分查找

DimiAsInteger,jAsInteger,keyAsInteger,mAsInteger

DimncAsInteger

IfNotsortedThen'進行對分查找時，需先對數(shù)據(jù)進行排序

MsgBox"進行對分查找時，需先對數(shù)據(jù)進行排序"

ExitSub'結(jié)束過程

EndIf

key=Val(Text2.Text)'輸入查找的數(shù)據(jù)

i=1

j=num

nc=0'查找次數(shù)nc

DoWhilei<=j'對分查找

nc=nc+1

m=Fix((i+j)/2)

Ifd(m)=keyThen‘找到了

Label6.Caption="在數(shù)組的第"+Str(m)+"個位置，共查找了"+Str(nc)+"次"

ExitSub

EndIf

Ifkey<d(m)Then'未找到，繼續(xù)查找

j=m-1

Else

i=m+1

EndIf

Loop

Label6.Caption="在數(shù)組中沒有找到數(shù)據(jù)"+Str(key)+"，共查找了"+Str(nc)+"次"

EndSub

（2）編寫程序代碼PrivateSubCom35

使用對分查找，每次都把規(guī)模縮小一半，效率比順序查找要高，但在進行對分查找前，需要將它排好序。

（3）運行調(diào)試程序

根據(jù)算法流程圖,填空完善已經(jīng)設(shè)計好的界面和部分代碼的順序查找和對分查找算法，并進行調(diào)試。使用對分查找，每次都把規(guī)模縮小一半，效率比順36課堂練習1.一個數(shù)組中含有元素A、B、C、D、E、F、G、H、I、J、K、L、M、N應用對分查找算法，查找目標為J時，會查經(jīng)哪幾個字母，如果查找的是Z呢？參考答案：

使用對分查找，查找目錄J時，會查經(jīng)H、L，查找Z，會查經(jīng)H、L、N，最后查找z未找到。

課堂練習1.一個數(shù)組中含有元素A、B、C、D、E、F、G、H372.數(shù)組元素為：Alice、Byron、Duane、Elaine、Floyd、Gene、Herry、Iris，請回答：

①哪個查找算法（順序查找和對分查找）能比較快找到名字Gene?

②哪個查找算法（順序查找和對分查找）能比較快找到名字Alice?

③哪個查找算法（順序查找和對分查找）能比較快地測定名字Bruce不存在?

④哪個查找算法（順序查找和對分查找）能比較快地測定名字Sue不存在?

⑤當利用順序查找算法查找名字Floyd時，查問了多少個數(shù)據(jù)？使用對分查找算法時，又要查問多少個數(shù)據(jù)？

2.數(shù)組元素為：Alice、Byron、Duane、Elai38參考答案：①查找Gene：對分查找快，對分查找3次，順序查找6次②查找Alice：順序查找快，順序查找1次，對分查找4次③查找Bruce：對分查找快，對分查找4次，順序查找8次④查找Sue：對分查找快，對分查找4次，順序查找8次⑤使用順序查找Floyd，查找了5個數(shù)據(jù)，使用對分查找，查問了1個數(shù)據(jù)

參考答案：①查找Gene：對分查找快，對分查找3次，順序查找393.對于有5000個元素的數(shù)組，使用對分查找，最多查問多少個數(shù)據(jù)？使用順序查找呢？試比較兩種查找算法的效率。

參考答案：

使用對分查找最多查問log25001個數(shù)據(jù)，使用順序查找最多查問5000次，所以對分查找效率比較高。

3.對于有5000個元素的數(shù)組，使用對分查找，最多查問多少個404.驗血問題的算法。有１０萬大軍三天后將要出發(fā)作戰(zhàn)。軍醫(yī)發(fā)現(xiàn)有一位士兵帶入了一種傳染病菌，三天后發(fā)作將傳染給全軍，使部隊喪失作戰(zhàn)能力，只有通過驗血才能發(fā)現(xiàn)誰是患者。