資源簡(jiǎn)介

(共17張PPT)
二分查找
贛科學(xué)技術(shù)版五年級(jí)下冊(cè)
第7課
二分查找
了解并掌握二分查找的基本思想
總結(jié)出二分查 找與順序查找的異同
熟練運(yùn)用二分查找解決實(shí)際問題
任務(wù)卡
一
試一試
下課啦，小藍(lán)和小紅玩起了猜數(shù)游戲。小藍(lán)從1到100 之間隨機(jī)選擇了 一個(gè)數(shù)字讓小紅猜，其中在小紅每次猜出一個(gè)數(shù)字后，小藍(lán)會(huì)給出相應(yīng)的提 示語。
提示語1:“不是，請(qǐng)重猜!”或“恭喜你，猜對(duì)啦!”。
提示語2:“不是，小了!”或“不是，大了!”或“恭喜你，猜對(duì)啦!”
假如小藍(lán)心里想的數(shù)字是59,小紅應(yīng)該如何設(shè)定猜數(shù)方案才能用最少的次數(shù)猜出59呢
一
試一試
如果按照提示語1玩猜數(shù)游戲時(shí)，小紅則需要把所有可能的數(shù)字一一列舉出來，如： 第一次：從1開始猜，“不是，請(qǐng)重猜!”;
第二次：2,“不是，請(qǐng)重猜!”;
…
第五十八次：58,“不是，請(qǐng)重猜!”;
第五十九次：59,“恭喜你，猜對(duì)啦!”。
綜上，小紅總共需要猜59次才能猜到小藍(lán)心里想的數(shù)字。
這是簡(jiǎn)單的查找，即我們上節(jié)課所學(xué)的順序查找方法。每次猜測(cè)都只能排除一個(gè)數(shù)字。如果小藍(lán)想的是100,那么小紅可能需要從1猜到100了。
因此，這種方法是要靠“運(yùn)氣”來決定猜測(cè)的次數(shù)，即由所猜測(cè)的數(shù)字在序列范圍中的位置所決定。
游戲一
一
試一試
如果按照提示語2玩猜數(shù)游戲時(shí)，小紅可以先猜數(shù)值范圍內(nèi)的中間值，再根據(jù)小藍(lán)提示的大小關(guān)系，選定新的查找范圍，這樣每次把查找的范圍變?yōu)榱嗽瓉淼囊话胱笥遥钡讲碌綌?shù)字。如：
(1)根據(jù)數(shù)字范圍是1~100,折中猜數(shù)字50,發(fā)現(xiàn)猜小了，因此要猜的數(shù)字在51 和100之間；
(2)根據(jù)數(shù)字范圍是51～100,折中猜數(shù)字75,發(fā)現(xiàn)猜大了，因此要猜的數(shù)字在51和75之間；
(3)根據(jù)數(shù)字范圍是51～75,折中猜數(shù)字63,發(fā)現(xiàn)猜大了，因此要猜的數(shù)字在51和63之間；
(4)根據(jù)數(shù)字范圍是51～63,折中猜數(shù)字57,發(fā)現(xiàn)猜小了，因此要猜的數(shù)字在57和63之間；
(5)根據(jù)數(shù)字范圍是57～63,折中猜數(shù)字60,發(fā)現(xiàn)猜大了，因此要猜的數(shù)字在57和60 之間；
(6)根據(jù)數(shù)字范圍是57～60,折中猜數(shù)字58,發(fā)現(xiàn)猜小了，因此要猜的數(shù)字在58和60之間；
(7)根據(jù)數(shù)字范圍是58～60,折中猜數(shù)字59,猜對(duì)啦。
游戲二
一
試一試
綜上，小紅只要猜7次就可以猜到小藍(lán)心里想的數(shù)字59。這顯然比一個(gè)個(gè)去試猜的效率要高很多。
游戲二
能夠這樣猜的原因是，要猜的數(shù)字在一個(gè)有序的數(shù)列中(1～100),并且可以獲得大 小關(guān)系。這樣，根據(jù)大小關(guān)系逐步縮小猜測(cè)范圍，最終猜中具體的數(shù)字。
二
做一做
綜上，小紅只要猜7次就可以猜到小藍(lán)心里想的數(shù)字59。這顯然比一個(gè)個(gè)去試猜的效率要高很多。
游戲二
能夠這樣猜的原因是，要猜的數(shù)字在一個(gè)有序的數(shù)列中(1～100),并且可以獲得大 小關(guān)系。這樣，根據(jù)大小關(guān)系逐步縮小猜測(cè)范圍，最終猜中具體的數(shù)字。
二
試一試
請(qǐng)把你們心中的猜數(shù)過程寫到書本31頁
如果小藍(lán)心里想的數(shù)字是77,你能在最快的時(shí)間猜出這個(gè)數(shù)嗎
二分查找
二分查找法也稱為折半查找法，它充分利用了元素間的次序關(guān)系，采用分治策略。它 是一種高效的查找方法，可以明顯減少比較次數(shù)，提高查找效率。但是，二分查找法查找 的前提條件是被查找的數(shù)據(jù)必須是有序的(可以從小到大排列，也可以從大到小排列)。
三
學(xué)一學(xué)
問題
假設(shè)某超市出售的糖果有9種不同的價(jià)格，分別為5,12,8,20,18,22,16, 30,36。現(xiàn)在要在其中查找價(jià)格為30元的糖果所在位置，運(yùn)用二分查找法應(yīng)該如何去查找呢
在查找數(shù)據(jù)時(shí)，如果數(shù)據(jù)已經(jīng)按照一定的順序排列好了，也可以利用上述類似的方 法，取大約居于查找范圍中間位置的數(shù)與要查的數(shù)進(jìn)行比較，然后根據(jù)大小調(diào)整查找范 圍，并最終找到該數(shù)據(jù)。這種查找數(shù)據(jù)的方法就是二分查找法。
三
學(xué)一學(xué)
首先，將這9種糖果的價(jià)格按從小到大進(jìn)行排序，確定待查價(jià)格所在的序列范圍，將 整個(gè)序列一分為二，確定查找的上限、下限與中間值，如圖。
(1)將待查價(jià)格30與中間值所指位置的價(jià)格“18”進(jìn)行比較，由于30>18,則30必然 在18之后的序列范圍中，因此取18的后半段為新的查找范圍，如圖。
三
學(xué)一學(xué)
繼續(xù)將待查價(jià)格30與后半段的中間值所指位置的價(jià)格“22”進(jìn)行比較，由于30>22,則 30必然在22之后的序列范圍中，因此取22的后半段為新的查找范圍，如圖。
二分查找的數(shù)據(jù)是有序的，怎樣讓一組無序的數(shù)據(jù)變成有序的，便于我們通過二分查找呢？
練一練
謝謝聆聽！
謝謝
21世紀(jì)教育網(wǎng)（www.21cnjy.com)
中小學(xué)教育資源網(wǎng)站
兼職招聘：
https://www.21cnjy.com/recruitment/home/admin

展開更多......

收起↑