資源簡(jiǎn)介

算法挑戰(zhàn)：二分查找法
(
今日任務(wù)：
)
今日我們來利用 scratch 進(jìn)行一次二分查找算法的探究。所謂二分查找法，就是這樣一 種查找思路，但是， 它的使用有一定的局限性，被查找的數(shù)列必須是有序數(shù)列。它的原理其 實(shí)很簡(jiǎn)單，可以這樣描述：將所查找的數(shù)字和有序數(shù)列中間的數(shù)字進(jìn)行比較，如果所查找數(shù)字大
于有序數(shù)列的中間位置數(shù)字， 那么就在有序數(shù)列的后半部分繼續(xù)進(jìn)行折半查找， 如果所查找數(shù)字小于
有序數(shù)列的中間位置數(shù)字，那么就在有序數(shù)列的前半部分繼續(xù)進(jìn)行折半查找， 以此往復(fù)，直到找到所
查找數(shù)字或者找完鏈表發(fā)現(xiàn)所查找數(shù)字不在數(shù)列中為止。
我們簡(jiǎn)單用圖形來解釋一下這個(gè)二分法是如何運(yùn)行的：
有這樣一個(gè)有序序列，數(shù)列中數(shù)字全部按照升序排列：
我們要在該數(shù)列中查找數(shù)字 11，我們來看看程序是怎樣運(yùn)行的！
Left=1 Mid=11 Right=20
1,3,5,7,11,33,37,42,56,79,88,102,113,117,128,142,155,161,177,208
Mid=（left+right）/2 四舍五入取整
(
11
≠
list
（
11
）且
11（
11
）
,
繼
續(xù)在前半部分查
)
Left=1
Mid=6
Right=10
1,3,5,7,11,33,37,42,56,79,88,102,113,117,128,142,155,161,177,208
(
11
≠
list
（
6
）且
11（
6
）
,
繼續(xù)在前半部分查找！
)
Left=1
Right=5
1,3,5,7,11,33,37,42,56,79,88,102,113,117,128,142,155,161,177,208
(
Mid=3
)
(
11
≠
list
（
3
）且
11>list
（
3
）
,
繼續(xù)在
前后半部分查
)
(
Mid=5
) (
沒有找到
n
) (
N
) (
Mid=
（
right+left
）
/2
四舍五
入取整
) (
Y
) (
right=mid-1
) (
Right
≥
left
Y
n=list(mid)
left=mid+1
N
N
nY
)
Left=4
Right=5
1,3,5,7,11,33,37,42,56,79,88,102,113,117,128,142,155,161,177,208
(
11=list
（
5
），
查找結(jié)束！
返回列表位置
5.
)
如果是按照順序查找法， 需要查找 5 次， 而用二分法只需要 4 次就可以查找到了， 如果有序數(shù)列更復(fù) 雜一些更長(zhǎng)一些， 二分法比順序查找法的優(yōu)勢(shì)就更加明顯！
(
本課重難點(diǎn)：
)
（1）了解二分查找的方法；
（2）能夠通過 scratch 編程實(shí)現(xiàn)二分查找法；
(
任務(wù)解讀
flowchart
：
)
開 始
(
鍵盤輸入
n
)
(
找到了，輸出
mid
值
)
結(jié) 束
(
跟我來挑戰(zhàn)
Follow
me
：
)
第一步：?jiǎn)?dòng) scratch 軟件；
第二步： 點(diǎn)擊上方的“文件”→ “保存”→保存到桌面，文件名： 二分查找 →點(diǎn)擊“保存”；
（第二步很很很重要，我希望所有的學(xué)生都能養(yǎng)成及時(shí)保存作品的好習(xí)慣！）
第三步： 首先我們先生成一個(gè)斐波那契數(shù)列
(
鍵盤輸入
n
)
程序較長(zhǎng)，我們單獨(dú)將二分法算法程序 定義為一個(gè)單獨(dú)地功能塊（子程序）， 用的時(shí)候調(diào)用就可以了！
(
還記得
left
和
right
、
mid
分別是什么？再提醒一下！
)
(
Right
≥
left
)
Mid=（right+left）/2 四舍五入取整
Count 是我用來記錄查找次數(shù)
的變量
(
找到了，輸出
mid
值
)
n=list(mid)
沒有找到 n
最后直接調(diào)用這個(gè)功能塊即可：
該程序的運(yùn)行結(jié)果是：
(
課后思考：
)
（1） 試著總結(jié)一下二分法的優(yōu)缺點(diǎn)？
優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；其缺點(diǎn)是要求待查表為有序表， 且插入刪除困難。因此， 折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。
（2） 想一想， 二分查找法的用途有哪些？二分查找法是最省優(yōu)查找算法嗎？ 有沒有更高 效的算法處理有序數(shù)列？
（3） 自己嘗試設(shè)計(jì)出一個(gè)隨即有序數(shù)列，嘗試用二分法去查找結(jié)果。

展開更多......

收起↑