第一篇：五種查找算法總結(jié)

五種查找算法總結(jié)

一、順序查找

條件：無序或有序隊(duì)列。

原理：按順序比較每個(gè)元素，直到找到關(guān)鍵字為止。

時(shí)間復(fù)雜度：O(n)二、二分查找（折半查找）

條件：有序數(shù)組

原理：查找過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結(jié)束；

如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。

如果在某一步驟數(shù)組為空，則代表找不到。

這種搜索算法每一次比較都使搜索范圍縮小一半。

時(shí)間復(fù)雜度：O(logn)三、二叉排序樹查找

條件：先創(chuàng)建二叉排序樹：

1.若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

2.若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

3.它的左、右子樹也分別為二叉排序樹。

原理：

在二叉查找樹b中查找x的過程為：

1.若b是空樹，則搜索失敗，否則：

2.若x等于b的根節(jié)點(diǎn)的數(shù)據(jù)域之值，則查找成功；否則：

3.若x小于b的根節(jié)點(diǎn)的數(shù)據(jù)域之值，則搜索左子樹；否則：

4.查找右子樹。

時(shí)間復(fù)雜度：

四、哈希表法（散列表）

條件：先創(chuàng)建哈希表（散列表）

原理：根據(jù)鍵值方式(Key value)進(jìn)行查找，通過散列函數(shù)，定位數(shù)據(jù)元素。

時(shí)間復(fù)雜度：幾乎是O(1)，取決于產(chǎn)生沖突的多少。

五、分塊查找

原理：將n個(gè)數(shù)據(jù)元素“按塊有序”劃分為m塊（m ≤ n）。

每一塊中的結(jié)點(diǎn)不必有序，但塊與塊之間必須“按塊有序”；即第1塊中任一元素的關(guān)鍵字都必須小于第2塊中任一元素的關(guān)鍵字；

而第2塊中任一元素又都必須小于第3塊中的任一元素，……。

然后使用二分查找及順序查找。

第二篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-查找算法

《數(shù)據(jù)結(jié)構(gòu)》 第八次實(shí)驗(yàn)報(bào)告

學(xué)生姓名 學(xué)生班級(jí) 學(xué)生學(xué)號(hào) 指導(dǎo)老師

重慶郵電大學(xué)計(jì)算機(jī)學(xué)院 計(jì)算機(jī)專業(yè)實(shí)驗(yàn)中心

一、實(shí)驗(yàn)內(nèi)容

1)有序表的二分查找

?建立有序表，然后進(jìn)行二分查找 2)二叉排序樹的查找 ?建立二叉排序樹，然后查找

二、需求分析

二分查找的基本思想是將n個(gè)元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,算法中止；如果xa[n/2],則只要在數(shù)組a的右半部搜索x.時(shí)間復(fù)雜度無非就是while循環(huán)的次數(shù)！總共有n個(gè)元素，漸漸跟下去就是n,n/2,n/4,....n/2^k（接下來操作元素的剩余個(gè)數(shù)），其中k就是循環(huán)的次數(shù) 由于你n/2^k取整后>=1 即令n/2^k=1 可得k=log2n,（是以2為底，n的對(duì)數(shù)）所以時(shí)間復(fù)雜度可以表示O()=O(logn)下面提供一段二分查找實(shí)現(xiàn)的偽代碼: BinarySearch(max,min,des)mid-<(max+min)/2 while(min<=max)mid=(min+max)/2 if mid=des then return mid elseif mid >des then max=mid-1 else min=mid+1 return max 折半查找法也稱為二分查找法，它充分利用了元素間的次序關(guān)系，采用分治策略，可在最壞的情況下用O(log n)完成搜索任務(wù)。它的基本思想是，將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止。如 果xa[n/2]，則我們只要在數(shù)組a的右 半部繼續(xù)搜索x。

三、概要設(shè)計(jì)

1、順序查找，在順序表R[0..n-1]中查找關(guān)鍵字為k的記錄，成功時(shí)返回找到的記錄位置，失敗時(shí)返回-1，具體的算法如下所示：

int SeqSearch(SeqList R,int n,KeyType k){

} int i=0;while(i

} if(i>=n){ } printf(“%d”,R[i].key);return i;return-1;else printf(“%d”,R[i].key);i++;

2、二分查找，在有序表R[0..n-1]中進(jìn)行二分查找，成功時(shí)返回記錄的位置，失敗時(shí)返回-1，具體的算法如下：

int BinSearch(SeqList R,int n,KeyType k){

} return-1;} int low=0,high=n-1,mid,count=0;while(low<=high){ mid=(low+high)/2;printf(“第%d次查找：在[ %d ,%d]中找到元素R[%d]:%dn ”,++count,low,high,mid,R[mid].key);if(R[mid].key==k)

return mid;high=mid-1;low=mid+1;if(R[mid].key>k)else

四、詳細(xì)設(shè)計(jì)

源代碼：

#include #include

static int a[1024],count=0;

void Find1(int low,int high,int x){ int mid;if(low<=high){ mid=(low+high)/2;count++;if(a[mid]>x)Find1(low,mid-1,x);else if(a[mid]

void Find2(int low,int high,int x){ int mid;if(low<=high){ mid=(low+high)/2;count++;if(a[mid]x)Find2(mid+1,high,x);else printf(“n查é找ò到?元a素?位?置?為a%d，?查é找ò次?數(shù)簓為a%d?！辍?mid,count);} else printf(“n查é找ò失骸?敗悒?，?查é找ò次?數(shù)簓為a%d?！辍?count);} int main(){ int n,x;printf(“請(qǐng)?輸?入?元a素?個(gè)?數(shù)簓:”);scanf(“%d”,&n);printf(“n請(qǐng)?按恪?從洙?高?到?低臺(tái)?或ò從洙?低臺(tái)?到?高?順3序ò輸?入?各÷元a素?(以?空?格?隔?開a):nn”);for(int i=1;i<=n;i++)scanf(“%d”,&a[i]);printf(“n請(qǐng)?輸?入?要癮查é找ò的?元a素?：阰”);scanf(“%d”,&x);if(a[1]<=a[n])Find1(1,n,x);else Find2(1,n,x);printf(“nn”);system(“pause”);}

五、心得體會(huì)

通過這次在實(shí)現(xiàn)順序和二分查找算法的過程中，讓我對(duì)順序和二分查找算法有了更多的了解。查找根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）的操作，應(yīng)用十分廣泛。順序查找是一種最簡單的查找方法。它的基本思路是：從表的一端開始,順序掃描線性表,依次將掃描到的關(guān)鍵字和給定值k相比較,若當(dāng)前掃描到的關(guān)鍵字與k相等,則查找成功；若掃描結(jié)束后,仍未找到關(guān)鍵字等于k的記錄,則查找失敗。二分查找也稱為折半查找要求線性表中的結(jié)點(diǎn)必須己按關(guān)鍵字值的遞增或遞減順序排列。它首先用要查找的關(guān)鍵字k與中間位置的結(jié)點(diǎn)的關(guān)鍵字相比較,這個(gè)中間結(jié)點(diǎn)把線性表分成了兩個(gè)子表,若比較結(jié)果相等則查找完成;若不相等,再根據(jù)k與該中間結(jié)點(diǎn)關(guān)鍵字的比較大小確定下一步查找哪個(gè)子表,這樣遞歸進(jìn)行下去,直到找到滿足條件的結(jié)點(diǎn)或者該線性表中沒有這樣的結(jié)點(diǎn)。在學(xué)習(xí)過程中，善于發(fā)現(xiàn)，會(huì)找到更多的捷徑。

六、附錄 運(yùn)行結(jié)果截圖。

第三篇：對(duì)分查找算法教案

對(duì)分查找算法教案

一、設(shè)計(jì)思想

對(duì)分查找是計(jì)算機(jī)科學(xué)中的一個(gè)基礎(chǔ)算法。對(duì)于一個(gè)基礎(chǔ)算法的學(xué)習(xí)，同樣可以讓學(xué)生在一定的情境下，經(jīng)歷分析問題、確定算法、編程求解等用計(jì)算機(jī)解決問題的基本過程。本堂課以一個(gè)游戲暖場，同時(shí)激活學(xué)生的思維，引導(dǎo)學(xué)生去探索游戲或生活背后的科學(xué)原理。為了讓學(xué)生在教師的引導(dǎo)下能自我解析算法的形成過程，本課分解了問題動(dòng)作，找出問題的全部可能情況，在對(duì)全部可能情況總結(jié)歸納的情況下，得出對(duì)分查找的基礎(chǔ)算法，最后在程序中得到實(shí)現(xiàn)，從而使學(xué)生建立起對(duì)分查找算法形成的科學(xué)邏輯結(jié)構(gòu)。

二、教材分析

本課的課程標(biāo)準(zhǔn)內(nèi)容：

（一）計(jì)算機(jī)解決問題的基本過程（1）結(jié)合實(shí)例，經(jīng)歷分析問題、確定算法、編程求解等用計(jì)算機(jī)解決問題的基本過程，認(rèn)識(shí)算法和程序設(shè)計(jì)在其中的地位和作用。

（三）算法與問題解決例舉 C 查找、排序與問題解決

（2）通過實(shí)例，掌握使用數(shù)據(jù)查找算法設(shè)計(jì)程序解決問題的方法。本課的《學(xué)科教學(xué)指導(dǎo)意見》內(nèi)容：基本要求：1.初步掌握對(duì)分查找算法。2.初步掌握對(duì)分查找算法的程序?qū)崿F(xiàn)。

教材內(nèi)容：第二章 算法實(shí)例 2.4.3對(duì)分查找和第五章5.4查找算法的程序?qū)崿F(xiàn)，課題定為對(duì)分查找算法及程序?qū)崿F(xiàn)，安排兩個(gè)課時(shí)，第一課時(shí)著重是對(duì)分查找算法的形成和初步程序?qū)崿F(xiàn)，第二課時(shí)利用對(duì)分查找算法解決一些實(shí)際問題的程序?qū)崿F(xiàn)，本教學(xué)設(shè)計(jì)為第一課時(shí)。

從《課程標(biāo)準(zhǔn)》和《學(xué)科教學(xué)指導(dǎo)意見》對(duì)本課教學(xué)內(nèi)容的要求來看，要求學(xué)生能從問題出發(fā)，通過相應(yīng)的科學(xué)步驟形成對(duì)分查找的算法。對(duì)學(xué)生來說，要求通過這一課時(shí)的學(xué)習(xí)能初步掌握或了解對(duì)分查找的前提條件、解決問題的對(duì)象，明確對(duì)分查找算法結(jié)構(gòu)和對(duì)分查找的意義。

三、學(xué)情分析

學(xué)生應(yīng)該已經(jīng)掌握程序設(shè)計(jì)的基本思想，掌握賦值語句、選擇語句、循環(huán)語句的基本用法和VB基本操作，這節(jié)課學(xué)生可能會(huì)遇到的最大問題是：如何歸納總結(jié)對(duì)分查找解決不同情況問題的一般規(guī)律，鑒于此，在教學(xué)中要積極引導(dǎo)學(xué)生采取分解動(dòng)作、比較遷移等學(xué)習(xí)策略。（說明：由于這個(gè)課是算法與程序設(shè)計(jì)課，對(duì)學(xué)生有一定的要求，學(xué)生至少應(yīng)該熟悉算法的基本概念，掌握順序結(jié)構(gòu)、分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，天津的學(xué)生雖然學(xué)的是Java,但是在算法這一塊上都是相通的，如果對(duì)算法流程，三種基本結(jié)構(gòu)原理和語句如果都掌握的話，理解這個(gè)課應(yīng)該沒什么大的問題，VB只是一個(gè)程序?qū)崿F(xiàn)的工具。但如果學(xué)生沒有較好的算法基礎(chǔ)，沒有前續(xù)的知識(shí)作輔墊，這節(jié)課會(huì)比較困難，教師就要靈活處理。）

四、教學(xué)目標(biāo)

知識(shí)與技能：理解對(duì)分查找的概念和特點(diǎn)，通過分步解析獲取對(duì)分查找的解題結(jié)構(gòu)，初步掌握對(duì)分查找算法的程序?qū)崿F(xiàn)。

過程與方法：通過分析多種不同的可能情況，逐步歸納對(duì)分查找的基本思想和方法，確定解題步驟。

情感態(tài)度與價(jià)值觀：通過實(shí)踐體驗(yàn)科學(xué)解題的重要性，增強(qiáng)效率意識(shí)和全局觀念，感受對(duì)分查找算法的魅力，養(yǎng)成始終堅(jiān)持、不斷積累才能獲得成功的意志品質(zhì)。

五、重點(diǎn)難點(diǎn)

教學(xué)重點(diǎn)和難點(diǎn)：分解并理解對(duì)分查找的過程。

六、教學(xué)策略與手段

1、教學(xué)線索：游戲引領(lǐng)---提出對(duì)分查找原理---解析對(duì)分查找的算法特征---實(shí)踐解決問題。

2、學(xué)習(xí)線索：分解問題---歸納問題---實(shí)踐提升，在三個(gè)階段的不斷推進(jìn)中明確對(duì)分查找算法，總結(jié)規(guī)律。

七、教學(xué)過程

1、新課導(dǎo)入

（1）熱身：游戲（2分鐘）教師展示一件特色物品，讓一個(gè)學(xué)生來猜這個(gè)物品的價(jià)格，其他學(xué)生只需要根據(jù)這個(gè)學(xué)生猜出的價(jià)格提示“高了”或是“低了”，如果學(xué)生能在約定次數(shù)內(nèi)猜對(duì)這個(gè)物品的價(jià)格，就把這件物品“贈(zèng)送”給他……。

（2）討論：你覺得怎么樣猜可以猜的快一點(diǎn)呢？有什么技巧嗎？你從這個(gè)游戲當(dāng)中得到什么啟示？(2分鐘)

（3）教師引導(dǎo)：這個(gè)世界不是缺少問題，而是缺少發(fā)現(xiàn)，其實(shí)在這個(gè)游戲的背后，含有一個(gè)非常經(jīng)典的算法。引出對(duì)分查找的的概念。(1分鐘)

2、新課：

教學(xué)步驟一：分析對(duì)分查找的原理和方法。（3分鐘）

（1）對(duì)分查找是效率很高的查找方法，但被查找的數(shù)據(jù)必須是有序的。

（2）首先將查找的數(shù)與有序數(shù)組內(nèi)處于中間位置的數(shù)據(jù)比較，如果中間位置上的數(shù)與查找的數(shù)不同，根據(jù)有序性，就可確定應(yīng)該在數(shù)組的前半部分還是后半部分繼續(xù)查找。

（3）在新確定的范圍內(nèi)，繼續(xù)按上述方法進(jìn)行查找，直到獲得最終結(jié)果。

教學(xué)步驟二：分解查找過程中可能出現(xiàn)的所有情況。（第一種情況5分鐘）

以規(guī)模為10的升序數(shù)組d為例：用一個(gè)數(shù)組d（1 to 10）來存放序列，用i表示查找范圍的第一個(gè)數(shù)組元素的下標(biāo)，j表示最后一個(gè)數(shù)組元素的下標(biāo),mid表示中間位置元素的下標(biāo)。（1）

第一種情況：要找的值在后半部分；

以查找鍵KEY=48為例分析

第一次查找：：

范圍d(1)～d(10),mid= └(1+10)/2┘, d(mid)

所以可以確定接下來要找的范圍是后半部分。

比較后i=mid+1

第二次查找：

范圍d(6)～d(10),mid= └(6+10)/2┘,d(mid)

所以可以確定接下來要找的范圍是后半部分。

比較后：i=mid+1

第三次比較：

范圍d(9)～d(10)，mid= └(9+10)/ ┘2，d(mid)=Key，找到了。

思考：如果要找的是52? i,j,mid分別是多少？ 總結(jié)一: 如果d(mid)

教學(xué)步驟三：繼續(xù)分解對(duì)分查找算法中包含的其他情況。（9分鐘）

討論:兩人為一合作小組，分別畫出key=17和key=20的查找示意圖,并用共同的智慧討論并回答以下兩個(gè)問題。

問題1:當(dāng)d(mid)>key時(shí)，新查找的范圍在哪里？i和j如何變化？

問題2:在什么情況下查找會(huì)結(jié)束？繼續(xù)進(jìn)行重復(fù)查找的條件是什么?

（2）

第二種情況：要找的值在前半部分；

以查找鍵KEY=17為例分析：

（3）第三種情況：要找的值找不到；以查找鍵KEY=20為例分析：

總結(jié)二：如果d(mid)>key ,新查找范圍為上半部分, i值不變，j=mid-1。

總結(jié)三：(1)找到了查找會(huì)結(jié)束;(2)在i<=j時(shí)重復(fù)查找,如果還是找不到,查找也會(huì)結(jié)束。

教學(xué)步驟四：對(duì)各種情況進(jìn)行歸納總結(jié)。（2分鐘）

（1）Key與d(mid)的大小比較影響i,j的取值的規(guī)律： i的取值規(guī)律：if d(mid)

j的取值規(guī)律：if d(mid)>key then j=mid-1,用分支結(jié)構(gòu)實(shí)現(xiàn)。

(2)繼續(xù)進(jìn)行重復(fù)查找的條件： i≤j，用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)。

教學(xué)步驟五：用流程圖來描述對(duì)分查找算法（3分鐘）

教學(xué)步驟六：對(duì)分查找算法的初步程序?qū)崿F(xiàn)。（9分鐘）

教師事先設(shè)計(jì)好VB窗體，學(xué)生只需在相應(yīng)的程序體輸入代表算法思想的關(guān)鍵語句。

附主要程序體：

Private Sub Command2_Click()

Dim key As Integer, mid As Integer, i As Integer, j As Integer key = Val(Text1.Text)i = 1: j = 10

Do While ____(1)_______ mid =(i + j)2 If d(mid)= key Then

Text2.Text = “找到了，是第” & mid & “個(gè)” Exit Sub End If If _____(2)_______ Then _____(3)_______ Else

_____(4)_______ End If Loop

Text2.Text = “對(duì)不起，找不到！” End Sub

教學(xué)步驟七：評(píng)價(jià)。（4分鐘）

用過程反饋表評(píng)價(jià)學(xué)生的程序?qū)崿F(xiàn)情況，學(xué)有余力的同學(xué)可以進(jìn)一步討論或?qū)嵺`問題：如果是降序序列，該怎么樣改動(dòng)程序？如果序列元素不是10個(gè)，而是100個(gè)或更多呢？

教學(xué)步驟八：盤點(diǎn)對(duì)分查找法的核心內(nèi)容,總結(jié)提升。（3分鐘）(1)采用對(duì)分查找的前提是數(shù)據(jù)序列必須是有序。

(2)由于對(duì)分查找過程中的每次比較都能使得搜索空間減半，對(duì)分查找將不會(huì)使用超過┌l(fā)og2(n+1)┐次來找到目標(biāo)值。

(3)提升對(duì)分查找算法的實(shí)際意義：同學(xué)們可能還沒有意識(shí)到對(duì)分查找是多么高效，那不妨設(shè)想一下在一個(gè)有一百萬個(gè)人名的電話簿中找一個(gè)名字，對(duì)分查找可以讓你不超過21次就能找到指定的名字。如果你能夠?qū)⑹澜缟纤械娜税凑招彰判颍敲茨阍?5次內(nèi)就能找到任何人。

教學(xué)步驟十：總結(jié)本課的科學(xué)解題過程。（2分鐘）

八、作業(yè)：

以下的三組元素序列能采用對(duì)分查找法來查找嗎？

(1)7，22，25，35，44，61，88，99,100

（2）22，46，77，89，67，99，33，20,98

（3）87，75，58，44，23，11，7，2，0，-8,-10

2、設(shè)計(jì)一個(gè)能用對(duì)分查找算法思想解決的實(shí)際問題，用自然語言描述即可，為下節(jié)課作準(zhǔn)備。

第四篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)(實(shí)驗(yàn)五：查找算法)

實(shí)驗(yàn)五 查找算法

實(shí)驗(yàn)項(xiàng)目：必做：順序查找、折半查找

選做：二叉查找樹 實(shí)驗(yàn)類型: 驗(yàn)證性 實(shí)驗(yàn)內(nèi)容：

順序查找：用數(shù)組或鏈表實(shí)現(xiàn)，數(shù)據(jù)有序或無序均可； 折半查找：必須用數(shù)組實(shí)現(xiàn)，且數(shù)據(jù)有序；

注意：提交的實(shí)驗(yàn)報(bào)告要顯示已有的數(shù)據(jù)元素、待查找的數(shù)據(jù)；應(yīng)包含查找成功、不成功的情況。

第五篇：《對(duì)分查找及其算法實(shí)現(xiàn)》教學(xué)設(shè)計(jì)

《對(duì)分查找及其算法實(shí)現(xiàn)》教學(xué)設(shè)計(jì)

湖北省巴東縣第一高級(jí)中學(xué) 劉少銀

一、教材學(xué)情分析

本次課是浙江版高中信息技術(shù)選修教材《算法與程序設(shè)計(jì)》第二章算法實(shí)例第四節(jié)查找中的一部分內(nèi)容。由于教材體系不適合校本實(shí)際，我們?cè)诮虒W(xué)過程中對(duì)教材體系作了如下調(diào)整。

講授順序：第一章 算法和算法的表示、第三章 面向?qū)ο蟮某绦蛟O(shè)計(jì)的基本知識(shí)、第四章 VB程序設(shè)計(jì)初步、第二章算法實(shí)例，第五章 算法實(shí)例的程序?qū)崿F(xiàn)穿插在相關(guān)內(nèi)容教學(xué)中完成。

因此在前期教學(xué)中學(xué)生已經(jīng)初步掌握了算法基礎(chǔ)及算法表示，VB程序設(shè)計(jì)初步等。本次課是讓學(xué)生掌握對(duì)分查找的思想及算法的實(shí)現(xiàn)。

二、教學(xué)目標(biāo)

知識(shí)與技能：理解對(duì)分查找的基本含義、方法，理解并能畫出對(duì)分查找的流程圖；

過程與方法：通過案例分析、直觀觀察，增強(qiáng)分析問題和解決問題的能力；

情感、態(tài)度與價(jià)值觀：感受信息技術(shù)與現(xiàn)實(shí)生活的關(guān)聯(lián)，激發(fā)對(duì)信息技術(shù)學(xué)科的求知欲，培養(yǎng)主動(dòng)學(xué)習(xí)和使用信息技術(shù)的意識(shí)；養(yǎng)成科學(xué)的學(xué)習(xí)態(tài)度，不迷信書本、不迷信權(quán)威。

三、教學(xué)重難點(diǎn)

教學(xué)重點(diǎn)：對(duì)分查找的基本方法及注意事項(xiàng)；

教學(xué)難點(diǎn)：對(duì)分查找算法的實(shí)現(xiàn)。

四、教學(xué)策略

·以“猜數(shù)”游戲?qū)?，引入?duì)分查找的概念；

·師生討論、生生討論、生生互助；分析、歸納、總結(jié)，理解并掌握對(duì)分查找的基本思想；

·采用分類研究、分享成果、課后練習(xí)等學(xué)習(xí)方法，理解對(duì)分查找方法及基本主要特征；

·采用自然評(píng)價(jià)、師生評(píng)價(jià)、生生評(píng)價(jià)等形式對(duì)學(xué)習(xí)進(jìn)行過程性評(píng)價(jià)。

五、教學(xué)過程

1．游戲激趣，釋疑對(duì)分查找

（三個(gè)程序圖片）

（初始界面）（人工猜數(shù)界面）（程序猜數(shù)界面）

準(zhǔn)備：幾張白紙，一支記號(hào)筆。啟動(dòng)猜數(shù)程序。

師：同學(xué)們好！大家看到前面的程序了嗎？它是一個(gè)什么程序呢？

同學(xué)：猜數(shù)游戲程序。

師：對(duì)，這是我用VB針對(duì)李泳主持的“幸運(yùn)52”中猜商品價(jià)格環(huán)節(jié)開發(fā)的一款程序，我先來說說針對(duì)主持人的部分：當(dāng)李泳宣布商品的價(jià)格范圍時(shí)，比如10000元內(nèi)，猜商品價(jià)格的人就可以在猜數(shù)范圍欄起始欄填上“0”，終至欄填“10000”，然后再將鼠標(biāo)移到猜數(shù)欄中單擊，程序即提示：“準(zhǔn)備！倒計(jì)時(shí)30秒”，當(dāng)單擊提示處，猜價(jià)格倒計(jì)時(shí)開始，猜價(jià)格人即可在猜數(shù)欄上填上所猜價(jià)格的數(shù)值，然后根據(jù)主持人的提示，選擇“不對(duì)”重新填寫商品價(jià)格或選擇“正確”讓所猜價(jià)格在“猜得結(jié)果”欄內(nèi)顯示正確結(jié)果并停止計(jì)時(shí)，提示欄中即顯示“您猜了M次，對(duì)了，恭喜您”。

師：大家覺得程序光有這樣的功能神奇嗎？

生：不神奇。

師：對(duì)，我也是這樣認(rèn)為的。這個(gè)程序神奇的地方在它能幫助猜商品價(jià)格人在規(guī)定的時(shí)間內(nèi)，根據(jù)主持人的提示準(zhǔn)確地猜出商品的價(jià)格，而且猜中率100%，所以現(xiàn)在“幸運(yùn)52”停播了，大家知道為什么嗎？

生：不知道。

師：就是因?yàn)槲议_發(fā)了這個(gè)程序呀！

生：（有的說信，有的抱著懷疑的態(tài)度不吭聲，也有說不信的）

師：有同學(xué)愿意上來試試嗎？

師：你在紙上寫下你的數(shù)值范圍和要猜的數(shù)，然后給大家看一下，別說出來，別讓電腦聽見了。

師：好，操作程序讓程序幫忙把寫的數(shù)找出來。

（程序找到正確的數(shù)）

師：神奇吧。

師：還有那位同學(xué)愿意試一下。

師：同樣，你還是先寫下要猜的數(shù)和范圍100～200，這次我們不讓大家看到他要猜的數(shù)，請(qǐng)大家?guī)兔τ浵鲁绦蛎看纬霈F(xiàn)的數(shù)字。

師：電腦程序也猜出了正確結(jié)果：132。

程序給出的數(shù)字是：

第一個(gè)數(shù)是：150

第二個(gè)數(shù)是：12

5第三個(gè)數(shù)是：137

第四個(gè)數(shù)是：1

31第五個(gè)數(shù)是：13

4最后是：13

2大家能看出什么規(guī)律了嗎？

生：看不出

師：單純從這幾個(gè)數(shù)當(dāng)中是看不出什么規(guī)律，現(xiàn)在我們依次把這些數(shù)放到數(shù)軸上，再看一下，大家看能找出什么規(guī)律呢？

同學(xué)發(fā)言??

師：大家認(rèn)為他說的怎樣？為什么不鼓掌呀！

師：對(duì)，正如剛才的同學(xué)說的那樣，程序是在給定范圍內(nèi)依次找中點(diǎn)方法來找到我們要找的最終數(shù)值，這就是我們今天要討論的一種新的查找方法：對(duì)分查找。

師：我們剛才的游戲中的數(shù)列是序的嗎？

生：是有序的，升序排列的。

師：如果是降序能用對(duì)分查找方式查找嗎？

生：能。

師：大家想一想，如果我們打亂數(shù)據(jù)的排序順序，在沒有排序的數(shù)列中能否用對(duì)分查找的方法，找到我們想找到的數(shù)據(jù)？

同學(xué)：不能。

師：對(duì)，這就是對(duì)分查找方法的一個(gè)特征，或稱為條件。因?yàn)槲覀兪歉鶕?jù)數(shù)據(jù)的大小找到它在數(shù)列中的位置。

【設(shè)計(jì)意圖】通過游戲和對(duì)程序給出數(shù)值在數(shù)軸上的分布分析，讓學(xué)生初步理解和掌握對(duì)分查找的方法及前提條件，為后一階段對(duì)分查找算法的實(shí)現(xiàn)作好鋪墊。

2．分析實(shí)例，實(shí)現(xiàn)對(duì)分查找算法

師：下面我們一起來看一下程序是怎樣一步一步的給出以上數(shù)據(jù)并最終找到“132”這個(gè)數(shù)的。

師：首先在100至200之間找中點(diǎn)，然后再用中點(diǎn)值150與所要找的數(shù)132比較，得出的結(jié)論是所要找的數(shù)在100至150之間的數(shù)，一下數(shù)值的范圍就縮小了一半，終止變量j的值就由200變成了150；第二次查找時(shí)，程序就給出100至150的中點(diǎn)值125；當(dāng)程序進(jìn)行第三次查找時(shí)，起始變量i的值就被修改為125，它們的中點(diǎn)值應(yīng)該是：（125+150）/2=137.5。有小數(shù)了，怎么辦？

生：??（有點(diǎn)茫然）

師：對(duì)于小數(shù)，程序可以繼續(xù)查找，但有可能要增加查找次數(shù)。為了保證在整數(shù)范圍內(nèi)查找，我們就要對(duì)含小數(shù)的中間值進(jìn)行處理：取整。大家還記得我們學(xué)過VB的取整函數(shù)嗎？

生：int。

師：對(duì)。即int（137．5），結(jié)果是多少？

生：137。

師：所以我們查找i到j(luò)范圍內(nèi)的中點(diǎn)值的表達(dá)式應(yīng)該為：m=int（（i+j）/2）。

師：依次類推，程序會(huì)依次給出131、134、132即找到了要找的數(shù)。

師：請(qǐng)同學(xué)們根據(jù)算法逐步求精的原則在下面畫出流程圖。

（展示如下流程圖，然后請(qǐng)同學(xué)完成完善對(duì)分查找的算法流程圖）

流程圖補(bǔ)充完善后的結(jié)果：

【設(shè)計(jì)意圖】通過對(duì)程序給出中間數(shù)的分析，幫助學(xué)生理解對(duì)分查找算法實(shí)現(xiàn)的方法，為學(xué)生順利完成對(duì)分查找算法流程圖給予理論與實(shí)踐上的支持。

3．推出特例，完善對(duì)分查找算法

師：同學(xué)們，剛才我們完成的對(duì)分查找的流程圖；下面請(qǐng)同學(xué)們用剛才的查找方法分析一下在199至200范圍內(nèi)要找200這個(gè)數(shù)，能找到嗎？為什么？如何解決這個(gè)問題？

（將教室內(nèi)學(xué)生按座位分成若干組，進(jìn)行討論。每個(gè)組推選一名小 組長，完成后作小組發(fā)言）

??

（每一小組完成發(fā)言后，老師或點(diǎn)評(píng)，或讓學(xué)生點(diǎn)評(píng)）

師：根據(jù)剛才同學(xué)的討論分析，那我們先前給出的流程圖就有了一些缺陷，怎么修改？

（在同學(xué)們的發(fā)言聲中，修改完善流程圖）

修改后的流程圖如下：

【設(shè)計(jì)意圖】給出特例，讓學(xué)生相互討論、互助學(xué)習(xí)，歸納總結(jié)出上述流程圖中出現(xiàn)問題的癥結(jié)所在，并給出正確的流程圖；由此可讓學(xué)生體驗(yàn)到科學(xué)探究的方法，從而培養(yǎng)學(xué)生的科學(xué)態(tài)度與探索精神。

六、課后作業(yè)

師：1．在前面的取整中我們用了取整函數(shù)int，大家想一想能不能用四舍五入函數(shù)處理？如果用四舍五入函數(shù)（round）處理，流程圖又將怎樣修改？

2．請(qǐng)看教材P40-43，比較我們所給出的流程圖與教材上的流程圖有什么差異？兩個(gè)流程圖最后結(jié)果是否一致，那個(gè)流程圖的結(jié)果有問題，問題是怎么造成的？請(qǐng)寫出一篇500—800字的小論文。

（提示：認(rèn)真閱讀教材P40至P43內(nèi)容，并分析教材中所給算法的邏輯錯(cuò)誤）

作業(yè)提交方式：電子郵件（校內(nèi)、校外均可）

郵件名稱：登分號(hào)+姓名+論文題目

作業(yè)提交地址：bdxyz@qq.com

【設(shè)計(jì)意圖】作業(yè)（1）擴(kuò)充課堂內(nèi)容，豐富學(xué)生知識(shí)面，豐富學(xué)生分別學(xué)習(xí)內(nèi)容；作業(yè)（2）通過兩個(gè)流程圖之間差異性比較，引導(dǎo)學(xué)生判別書本上所給出流程圖的邏輯錯(cuò)誤，從而培養(yǎng)學(xué)生：1．科學(xué)的學(xué)習(xí)態(tài)度和精神，不迷信教材、不迷信權(quán)威；2．運(yùn)用論文等形式來表達(dá)自己觀點(diǎn)；3．通過學(xué)生自己的分析、探索，找出教材中的錯(cuò)誤。

七、教學(xué)反思

整節(jié)課充滿了笑聲和掌聲，課堂氣氛活躍，學(xué)生參與度高。老師的主導(dǎo)作用和學(xué)生的主體地位得到了充分的體現(xiàn)。學(xué)生在師生互動(dòng)、生生討論、生生互助中比較好地掌握了對(duì)分查找的思想和算法實(shí)現(xiàn)，教學(xué)效果好。但由于時(shí)間關(guān)系，沒有將程序的源代碼展示給學(xué)生，讓學(xué)生有一種意猶未盡的感覺是本次課的一個(gè)缺憾。