高中信息技術(shù)選修1：算法與程序設(shè)計 2.4 查找-“江南聯(lián)賽”一等獎

查找浙江教育出版社信息技術(shù)選修1《算法與程序設(shè)計》第二章第4節(jié)撫順市第十中學(xué)宋莉莉張學(xué)友演唱會逃犯被抓網(wǎng)友：史上抓逃犯最多的歌手新聞報道4月7日晚張學(xué)友在南昌開演唱會。一逃犯敖某特意從外地趕來。在演唱會開演后沒多久，根據(jù)演唱會的安保人像識別功能警方成功鎖定了這名在逃人員，在演出中心的看臺上將這名男子帶離現(xiàn)場。從今年的4月到6月間的四場演唱會上成功抓獲4名罪犯新聞報道5月5日晚張學(xué)友在贛州演唱會上警方在安檢過程中利用高科技手段現(xiàn)場抓獲網(wǎng)逃1名（劉某）!張學(xué)友演唱會逃犯被抓網(wǎng)友：史上抓逃犯最多的歌手通過安檢時系統(tǒng)報警5月20日晚張學(xué)友在浙江嘉興體育館開演唱會。當(dāng)天晚上，前來觀看演出的歌迷陸續(xù)通過安檢進(jìn)場，山東人于某也是等候進(jìn)場人流中的一員。在他通過安檢門后幾分鐘，系統(tǒng)便發(fā)出預(yù)警，即此人為網(wǎng)上在逃人員。最后警方選擇在演唱會結(jié)束散場后，將其抓獲。新聞報道張學(xué)友演唱會逃犯被抓網(wǎng)友：史上抓逃犯最多的歌手通過安檢門時，系統(tǒng)發(fā)出報警新聞報道張學(xué)友演唱會逃犯被抓網(wǎng)友：史上抓逃犯最多的歌手金華演唱會為什么計算機(jī)系統(tǒng)能幫助公安部門快速的查找到犯罪人呢？思考回答聯(lián)網(wǎng)的數(shù)據(jù)庫強(qiáng)大的查找算法快速的目標(biāo)對比精準(zhǔn)的鎖定位置在你生活和學(xué)習(xí)中有沒有查找的經(jīng)歷?思考回答查找在我們的生活中無處不在吃穿住行什么是查找？查找是一種查詢數(shù)據(jù)的技術(shù)，其目標(biāo)是能以比較少的步驟或較短的時間找到所需的對象。知識鏈接還記得這部動畫電影嗎？思考回答瘋狂動物城以查找“閃電”為例來開啟我們今天的查找之旅！新知學(xué)習(xí)確定查找目標(biāo)發(fā)現(xiàn)目標(biāo)接下來，來自《瘋狂動物城》的6位演員將依次登場亮相，我們查找一下有沒有“閃電”呢？查找之旅出場順序?yàn)椋?計算機(jī)如何解決該類問題呢？查找“閃電”的過程，計算機(jī)是如何表示的呢？數(shù)組定義一個名稱為d規(guī)模為6的數(shù)組數(shù)組元素表示每位演員d(1)d(2)d(3)d(4)d(5)d(6)d(1)d(2)d(3)d(4)d(5)d(6)解決問題d(1)

d(2)

d(3)

d(4)

d(5)

d(6)下標(biāo)代表存儲位置Key:存儲位置i為：

d確定查找目標(biāo)發(fā)現(xiàn)目標(biāo)5查找之旅（查找鍵）步驟：1、確定目標(biāo)key。

2、作比較d(i)=key?3、輸出結(jié)果。輸出結(jié)果作比較32653206130321725262589326548327052確定目標(biāo)Key:d13845672d(1)<>key沒找到d(2)<>key沒找到d(3)<>key沒找到d(4)<>key沒找到d(5)<>key沒找到d(6)=key到此處已找到查找過程結(jié)束存儲位置i為：

6483270523265輸出結(jié)果作比較d(i)=key?實(shí)例分析在規(guī)模為8的數(shù)組中查找3265。32053206130321725262589326548327052確定目標(biāo)Key:d13845672d(1)<>key沒找到d(2)<>key沒找到d(3)<>key沒找到d(4)<>key沒找到d(5)<>key沒找到d(6)<>key沒找到存儲位置i為：

0d(7)<>key沒找到d(8)<>key沒找到當(dāng)查找完整個數(shù)組元素后仍無法找到目標(biāo)key，即本數(shù)組中無要查找數(shù)據(jù)，則輸出0已經(jīng)是最后一個數(shù)據(jù)了，查找結(jié)束實(shí)例分析在規(guī)模為8的數(shù)組中查找3205作比較d(i)=key?輸出結(jié)果剛才我們的所有查找是怎樣進(jìn)行的呢？提示：1、從第一個數(shù)組元素開始

2、逐一比較順序查找思考回答提示：1、從第一個數(shù)組元素開始

2、逐一比較什么是順序查找？知識鏈接在一組數(shù)據(jù)中進(jìn)行查找時從數(shù)據(jù)的第一個元素開始，按照這組數(shù)據(jù)的順序查找指定的目標(biāo)值；每個數(shù)據(jù)逐個與目標(biāo)值進(jìn)行比較。（1）若某個數(shù)據(jù)與目標(biāo)值相等，則查找成功，找到目標(biāo)值的位置；（2）反之則表示被查數(shù)據(jù)中不存在該目標(biāo)值，查找不成功。1次順序查找次數(shù)的探究數(shù)組規(guī)模最少次數(shù)（最幸運(yùn)的次數(shù)）最多次數(shù)（最糟糕的次數(shù)）68n16181n順序查找算法的流程圖未找到，輸出結(jié)果：0說明：i—數(shù)組d(i)中的下標(biāo)n—數(shù)組的規(guī)模數(shù)key——查找鍵數(shù)組d(i)的第一個數(shù)組元素判斷是否是最后一個數(shù)組元素與目標(biāo)值比較查找下一個看視頻，在教師指導(dǎo)下完成游戲。游戲時間任務(wù)一：請猜出張藝興抽出中的牌。要求：1、兩名同學(xué)參加（只有三次機(jī)會）。2、一名同學(xué)扮演極限男人幫的猜數(shù)字的人。3、一名同學(xué)扮演水兵旗手，只能提示另一個同學(xué)猜的數(shù)字是大了還是小了。游戲時間答案揭曉張藝興抽出的牌是：任務(wù)二：修改游戲規(guī)則。請同學(xué)們幫助“極限男人幫”的成員設(shè)計一種算法，快速的猜中80個數(shù)中抽到任意的一個數(shù)，以便盡快救出其他兩位成員。要求適合任意數(shù)，找到這個數(shù)用的次數(shù)最少。小組探究修改游戲規(guī)則活動方式：以組為單位討論（前后四人一組）。結(jié)果呈現(xiàn)：每組將結(jié)果總結(jié)匯報，選一人向全班匯報。用自然語言描述你的查找方式。成果交流以猜78為例匯報內(nèi)容：1、查找方法2、查找的最多次數(shù)驗(yàn)證算法：1、兩名同學(xué)參加。（一名抽數(shù)，一名猜數(shù)）2、抽數(shù)同學(xué)，通過提示另一個同學(xué)“大了”或“小了”，完成猜數(shù)游戲。3、猜數(shù)同學(xué)，在規(guī)定次數(shù)內(nèi)完成猜數(shù)游戲。游戲時間剛才我們的所有查找是怎樣進(jìn)行的呢？提示：從數(shù)組的中間位置的元素起與目標(biāo)值比較

對分查找提示：從數(shù)組的中間位置的元素起與目標(biāo)值比較

思考回答對分查找對數(shù)據(jù)有要求嗎？有序性下列規(guī)模為8數(shù)組能用對分查找法算法查找嗎？262572388155962練習(xí)1練習(xí)2815252638596272能夠用對分查找的數(shù)組應(yīng)該具有什么特征呢？對分查找對數(shù)據(jù)有要求嗎？下列規(guī)模為8數(shù)組能用對分查找法算法查找嗎？262572388155962練習(xí)1練習(xí)2815252638596272如果想使用對分查找算法查找練習(xí)1中的數(shù)據(jù)該怎么辦呢？排序你學(xué)過哪種排序算法？冒泡排序選擇排序什么是對分查找？對分查找（又叫二分查找、折半查找）是一種快速從一個有序數(shù)組中找到某個元素位置的查找算法。知識鏈接前提條件：被查找的數(shù)據(jù)必須是有序的?；舅枷耄海?）首先將查找的數(shù)與有序數(shù)組內(nèi)處于中間位置的數(shù)據(jù)比較，如果中間位置上的數(shù)與查找的數(shù)不同，根據(jù)有序性，就可以確定下次應(yīng)該在數(shù)組的前半部分還是在后半部分繼續(xù)查找。（2）在新確定的范圍內(nèi)，繼續(xù)按上述方法進(jìn)行查找，直到獲得最終結(jié)果。1015171822273545485265677285979812345678910111213141516d用對分查找算法解決查找問題數(shù)組規(guī)模為16查找35實(shí)例分析對分查找算法是如何實(shí)現(xiàn)的？明確問題：1、解決該問題是否可以用對分查找？解題思路：查找過程可以，數(shù)據(jù)具有有序性（升序）確定目標(biāo)key=35作比較

輸出結(jié)果用i表示查找范圍的起點(diǎn)位置下標(biāo)，用j表示查找范圍終止位置的下標(biāo)，用m表示查找范圍中間位置元素的下標(biāo)2、怎樣表示各點(diǎn)位置？1015171822273545485265677285979812345678910111213141516d←i←m←j用對分查找算法解決查找問題用i表示查找范圍的起點(diǎn)位置下標(biāo)，j表示終止位置的下標(biāo)，m表示中間位置元素的下標(biāo)。第一次查找確定起點(diǎn)位值為i，終點(diǎn)位置為j。即i=1，j=16比較范圍d(1)~d(16)，在16個數(shù)據(jù)中查找中間值位置：m=（i+j）\2=(1+16)\2(取整)=845>35（d(8)>key）即d(m)>key所以可以確定接下來的查找在前半部分。數(shù)組規(guī)模為16查找鍵key=35起點(diǎn)位置下標(biāo)終止位置下標(biāo)中間位置下標(biāo)10151718222735454852656772859798d(8)>key比較后：j=m-1實(shí)例分析101517182227351234567910111213141516d←i←m←j第二次查找確定新起點(diǎn)位值為i，新終點(diǎn)位置為j。即i=1，j=7比較范圍d(1)~d(7)，在7個數(shù)據(jù)中查找中間值位置：m=（i+j）\2=(1+7)\2(取整)=418<35即d(4)<key所以可以確定接下來的查找在后半部分。用對分查找算法解決查找問題數(shù)組規(guī)模為16key=35起點(diǎn)位置下標(biāo)終止位置下標(biāo)中間位置下標(biāo)10151718222735d(4)<key比較后：i=m+1實(shí)例分析222735567d←i←m←j第三次查找確定新起點(diǎn)位值為i，新終點(diǎn)位置為j。即i=5，j=7比較范圍d(5)~d(7)，在3個數(shù)據(jù)中查找中間值位置：m=（i+j）\2=(5+7)\2(取整)=627<35（d(6)<key）即d(m)<key所以可以確定接下來的查找在后半部分。用對分查找算法解決查找問題數(shù)組規(guī)模為16key=35d(6)<key222735實(shí)例分析3512345678910111213141516d←I,j,m第四次查找確定新起點(diǎn)位值為i，新終點(diǎn)位置為j。即i=7，j=7比較范圍d(7)，在1個數(shù)據(jù)中查找中間值位置：m=（i+j）\2=(7+7)\2(取整)=735＝35（d(7)＝key）即d(m)＝key找到目標(biāo)用對分查找算法解決查找問題數(shù)組規(guī)模為16key=3535d(7)=key輸出存儲位置為：7實(shí)例分析查找次數(shù)探究1015171822273545485265677285979812345678910111213141516d實(shí)例分析假設(shè)將目標(biāo)值key=32，那么查找結(jié)果是什么？找不到，輸出存儲位置為：0對分查找次數(shù)的探究最幸運(yùn)多少次？最糟糕多少次？Log2

n1對分查找流程圖i←1,j←n開始用i表示起點(diǎn)，用j表示終點(diǎn)判斷起點(diǎn)與終點(diǎn)是否在同一位置上確定中間點(diǎn)的位置中間位置的值與目標(biāo)值比較確定下次查找的起點(diǎn)或終點(diǎn)相等輸出m的值當(dāng)查詢到最后仍未找到時，輸出0順序查找與對分查找比較順序查找優(yōu)點(diǎn)缺點(diǎn)對分查找優(yōu)點(diǎn)缺點(diǎn)比較次數(shù)，查找速度快要查找的數(shù)據(jù)必須數(shù)據(jù)較

時，查找速度快數(shù)據(jù)較時，查找速度慢少多少有序?qū)嵺`體驗(yàn)?zāi)炒未髴?zhàn)前夕，10萬大軍將在三天后出