學(xué)科教育論文-在游戲中學(xué)習(xí)二分查找的算法思想摘要：本文的主要內(nèi)容包括：二分查找的算法思想；講解中不易理解、掌握的原因；通過游戲理解算法。通過游戲中學(xué)習(xí)二分查找的算法思想教學(xué)過程，讓學(xué)生參與其中，體驗(yàn)過程，分析原因，得出結(jié)論。關(guān)鍵詞：二分查找游戲理解算法游戲一、二分查找的算法思想在已經(jīng)排好序的數(shù)列中，首先找到中間的記錄，這時(shí)可能會(huì)出現(xiàn)三種情況之一（假設(shè)按升序排列）。1)該記錄對(duì)應(yīng)字段的值小于查找關(guān)鍵字，此時(shí)應(yīng)在前半部分記錄中繼續(xù)查找。2)該記錄對(duì)應(yīng)字段的值大于查找關(guān)鍵字，此時(shí)應(yīng)在后半部分記錄中繼續(xù)查找。3)該記錄對(duì)應(yīng)字段的值等于查找關(guān)鍵字，那么就已找到了查找目標(biāo)，查找結(jié)束。如果出現(xiàn)前兩種情況，則繼續(xù)在前半部分或后半部分內(nèi)進(jìn)行對(duì)半查找，直到出現(xiàn)第三種情況為止。如果沿指定方向測(cè)試完成所有記錄時(shí)仍未出現(xiàn)第三種情況，則表示未找到查找目標(biāo)，查找也結(jié)束。二、講解中不易理解、掌握的原因單看這一串算法思想的解釋有些學(xué)生便有些沒有耐心了，更不用說去掌握應(yīng)用了。或者有些人生硬地記住了這些原理卻沒有真正地理解，寫程序時(shí)也會(huì)漏洞百出的。只有讓學(xué)親身體會(huì)了查找的過程，才能理解算法思想，才能想到編程時(shí)的條件設(shè)置及注意點(diǎn)。從而真正達(dá)到理解、應(yīng)用的最終目標(biāo)。三、通過游戲理解算法游戲過程如下：第一步：把10名同學(xué)按身高從低到高排成一列，并依次排號(hào)為1到10號(hào)。并另找一位學(xué)生，稱為X，找一找10人中有無與X同樣身高的。若有則輸出他的號(hào)碼。第二步：讓其它學(xué)生自己想方法去解決這個(gè)問題。討論之后學(xué)生得出了這樣一個(gè)結(jié)論：把X與這一列中1號(hào)到10號(hào)的每個(gè)人依次比較過去，便有結(jié)論出來了。教師總結(jié)：這種方法叫順序比較法，可以達(dá)到目的，但是程序的復(fù)雜度比較高，比如說有1000人或者有10000人或者更多的話，這種方法就體現(xiàn)不出優(yōu)越性了。如何更快更簡(jiǎn)便地得到結(jié)論呢？這時(shí)教師引入二分法的思想：從10個(gè)中找出中間位置的一位同學(xué)與X進(jìn)行比較。有三種結(jié)論：1、若相等則表示找到，停止程序。2、若比X高，那么與X等高的得在中間往后的這部分人中找。3、若比X低，那么與X等高的得在中間往前的這部分人中找。在2或3中又重復(fù)同一過程。第三步：游戲分進(jìn)行3次第一次游戲選擇一個(gè)學(xué)生X，其身高與九號(hào)學(xué)生剛好相同（假設(shè)不知道）游戲過程如下：1號(hào)2號(hào)3號(hào)4號(hào)5號(hào)6號(hào)7號(hào)8號(hào)9號(hào)10號(hào)隊(duì)首：1號(hào)隊(duì)尾：10號(hào)找到中位置MID=（1+10）2=5號(hào)因?yàn)閄5號(hào)所以只能舍棄前半部分，在后半部分找，于是只剩下6號(hào)7號(hào)8號(hào)9號(hào)10號(hào)隊(duì)首：6號(hào)隊(duì)尾：10號(hào)找到中間位置：MID=（6+10）2=8號(hào)因?yàn)閄8號(hào)所以只能舍棄前半部分,在后半部分找,于是只剩下9號(hào)10號(hào)隊(duì)首：9號(hào)隊(duì)尾：10號(hào)找到中間位置：MID=（9+10）2=9號(hào)因?yàn)閄=9號(hào),找到。停止尋找。在這輪游戲中可以發(fā)現(xiàn)從第二次開始每次的隊(duì)首都是前一次求得的中間值加1得到的。也可理解為從中間一項(xiàng)往后開始下一次尋找。第二次游戲：假設(shè)X的身高小于所有隊(duì)列中的同學(xué)1號(hào)2號(hào)3號(hào)4號(hào)5號(hào)6號(hào)7號(hào)8號(hào)9號(hào)10號(hào)隊(duì)首：1號(hào)隊(duì)尾：10號(hào)找到中位置MID=（1+10）2=5號(hào)因?yàn)閄5號(hào)所以要舍棄中間往后的部分,在前半部分找,于是剩下:1號(hào)2號(hào)3號(hào)4號(hào)隊(duì)首：1號(hào)隊(duì)尾：4號(hào)找到中位置MID=（1+4）2=2號(hào)因?yàn)閄2號(hào)所以要舍棄中間往后的部分,在前半部分找,于是剩下:1號(hào)隊(duì)首：1號(hào)隊(duì)尾：1號(hào)找到中間位置：MID=（1+1）2=1號(hào)因?yàn)閄5號(hào)所以要舍棄中間往前的部分,在后半部分找,于是剩下:6號(hào)7號(hào)8號(hào)9號(hào)10號(hào)隊(duì)首：6號(hào)隊(duì)尾：10號(hào)找到中位置MID=（6+10）2=8號(hào)因?yàn)閄8號(hào)所以要舍棄中間往前的部分,在后半部分找,于是剩下:9號(hào)10號(hào)隊(duì)首：9號(hào)隊(duì)尾：10號(hào)找到中位置MID=（9+10）2=9號(hào)因?yàn)閄9號(hào)所以要舍棄中間往前的部分,在后半部分找,于是剩下:10號(hào)隊(duì)首：10號(hào)隊(duì)尾：10號(hào)找到中位置MID=（10+10）2=10號(hào)因?yàn)閄10號(hào)所以要舍棄中間往前的部分,在后半部分找,而后面已無學(xué)生了,也就是說在隊(duì)列中找不到與X相同身高的學(xué)生.。若按照前面的方法，可得如下的結(jié)論：隊(duì)首：11號(hào)隊(duì)尾：10號(hào)因?yàn)殛?duì)列中最小是1號(hào)，最大是10號(hào)，不存在11號(hào)，可見出列了，也可知隊(duì)列中沒有與X身高相同的同