第一篇：五種查找算法總結

五種查找算法總結

一、順序查找

條件：無序或有序隊列。

原理：按順序比較每個元素，直到找到關鍵字為止。

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

條件：有序數組

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

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

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

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

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

條件：先創建二叉排序樹：

1.若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

2.若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

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

原理：

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

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

2.若x等于b的根節點的數據域之值，則查找成功；否則：

3.若x小于b的根節點的數據域之值，則搜索左子樹；否則：

4.查找右子樹。

時間復雜度：

四、哈希表法（散列表）

條件：先創建哈希表（散列表）

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

時間復雜度：幾乎是O(1)，取決于產生沖突的多少。

五、分塊查找

原理：將n個數據元素“按塊有序”劃分為m塊（m ≤ n）。

每一塊中的結點不必有序，但塊與塊之間必須“按塊有序”；即第1塊中任一元素的關鍵字都必須小于第2塊中任一元素的關鍵字；

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

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

第二篇：數據結構實驗報告-查找算法

《數據結構》 第八次實驗報告

學生姓名 學生班級 學生學號 指導老師

重慶郵電大學計算機學院 計算機專業實驗中心

一、實驗內容

1)有序表的二分查找

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

二、需求分析

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

三、概要設計

1、順序查找，在順序表R[0..n-1]中查找關鍵字為k的記錄，成功時返回找到的記錄位置，失敗時返回-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]中進行二分查找，成功時返回記錄的位置，失敗時返回-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

四、詳細設計

源代碼：

#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，?查é找ò次?數簓為a%d。￡”,mid,count);} else printf(“n查é找ò失骸?敗悒?，?查é找ò次?數簓為a%d。￡”,count);} int main(){ int n,x;printf(“請?輸?入?元a素?個?數簓:”);scanf(“%d”,&n);printf(“n請?按恪?從洙?高?到?低臺?或ò從洙?低臺?到?高?順3序ò輸?入?各÷元a素?(以?空?格?隔?開a):nn”);for(int i=1;i<=n;i++)scanf(“%d”,&a[i]);printf(“n請?輸?入?要癮查é找ò的?元a素?：阰”);scanf(“%d”,&x);if(a[1]<=a[n])Find1(1,n,x);else Find2(1,n,x);printf(“nn”);system(“pause”);}

五、心得體會

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

六、附錄 運行結果截圖。

第三篇：對分查找算法教案

對分查找算法教案

一、設計思想

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

二、教材分析

本課的課程標準內容：

（一）計算機解決問題的基本過程（1）結合實例，經歷分析問題、確定算法、編程求解等用計算機解決問題的基本過程，認識算法和程序設計在其中的地位和作用。

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

（2）通過實例，掌握使用數據查找算法設計程序解決問題的方法。本課的《學科教學指導意見》內容：基本要求：1.初步掌握對分查找算法。2.初步掌握對分查找算法的程序實現。

教材內容：第二章 算法實例 2.4.3對分查找和第五章5.4查找算法的程序實現，課題定為對分查找算法及程序實現，安排兩個課時，第一課時著重是對分查找算法的形成和初步程序實現，第二課時利用對分查找算法解決一些實際問題的程序實現，本教學設計為第一課時。

從《課程標準》和《學科教學指導意見》對本課教學內容的要求來看，要求學生能從問題出發，通過相應的科學步驟形成對分查找的算法。對學生來說，要求通過這一課時的學習能初步掌握或了解對分查找的前提條件、解決問題的對象，明確對分查找算法結構和對分查找的意義。

三、學情分析

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

四、教學目標

知識與技能：理解對分查找的概念和特點，通過分步解析獲取對分查找的解題結構，初步掌握對分查找算法的程序實現。

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

情感態度與價值觀：通過實踐體驗科學解題的重要性，增強效率意識和全局觀念，感受對分查找算法的魅力，養成始終堅持、不斷積累才能獲得成功的意志品質。

五、重點難點

教學重點和難點：分解并理解對分查找的過程。

六、教學策略與手段

1、教學線索：游戲引領---提出對分查找原理---解析對分查找的算法特征---實踐解決問題。

2、學習線索：分解問題---歸納問題---實踐提升，在三個階段的不斷推進中明確對分查找算法，總結規律。

七、教學過程

1、新課導入

（1）熱身：游戲（2分鐘）教師展示一件特色物品，讓一個學生來猜這個物品的價格，其他學生只需要根據這個學生猜出的價格提示“高了”或是“低了”，如果學生能在約定次數內猜對這個物品的價格，就把這件物品“贈送”給他……。

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

（3）教師引導：這個世界不是缺少問題，而是缺少發現，其實在這個游戲的背后，含有一個非常經典的算法。引出對分查找的的概念。(1分鐘)

2、新課：

教學步驟一：分析對分查找的原理和方法。（3分鐘）

（1）對分查找是效率很高的查找方法，但被查找的數據必須是有序的。

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

（3）在新確定的范圍內，繼續按上述方法進行查找，直到獲得最終結果。

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

以規模為10的升序數組d為例：用一個數組d（1 to 10）來存放序列，用i表示查找范圍的第一個數組元素的下標，j表示最后一個數組元素的下標,mid表示中間位置元素的下標。（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分別是多少？ 總結一: 如果d(mid)

教學步驟三：繼續分解對分查找算法中包含的其他情況。（9分鐘）

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

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

問題2:在什么情況下查找會結束？繼續進行重復查找的條件是什么?

（2）

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

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

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

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

總結三：(1)找到了查找會結束;(2)在i<=j時重復查找,如果還是找不到,查找也會結束。

教學步驟四：對各種情況進行歸納總結。（2分鐘）

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

j的取值規律：if d(mid)>key then j=mid-1,用分支結構實現。

(2)繼續進行重復查找的條件： i≤j，用循環結構實現。

教學步驟五：用流程圖來描述對分查找算法（3分鐘）

教學步驟六：對分查找算法的初步程序實現。（9分鐘）

教師事先設計好VB窗體，學生只需在相應的程序體輸入代表算法思想的關鍵語句。

附主要程序體：

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 & “個” Exit Sub End If If _____(2)_______ Then _____(3)_______ Else

_____(4)_______ End If Loop

Text2.Text = “對不起，找不到！” End Sub

教學步驟七：評價。（4分鐘）

用過程反饋表評價學生的程序實現情況，學有余力的同學可以進一步討論或實踐問題：如果是降序序列，該怎么樣改動程序？如果序列元素不是10個，而是100個或更多呢？

教學步驟八：盤點對分查找法的核心內容,總結提升。（3分鐘）(1)采用對分查找的前提是數據序列必須是有序。

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

(3)提升對分查找算法的實際意義：同學們可能還沒有意識到對分查找是多么高效，那不妨設想一下在一個有一百萬個人名的電話簿中找一個名字，對分查找可以讓你不超過21次就能找到指定的名字。如果你能夠將世界上所有的人按照姓名排序，那么你在35次內就能找到任何人。

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

八、作業：

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

(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、設計一個能用對分查找算法思想解決的實際問題，用自然語言描述即可，為下節課作準備。

第四篇：數據結構實驗指導(實驗五：查找算法)

實驗五 查找算法

實驗項目：必做：順序查找、折半查找

選做：二叉查找樹 實驗類型: 驗證性 實驗內容：

順序查找：用數組或鏈表實現，數據有序或無序均可； 折半查找：必須用數組實現，且數據有序；

注意：提交的實驗報告要顯示已有的數據元素、待查找的數據；應包含查找成功、不成功的情況。

第五篇：《對分查找及其算法實現》教學設計

《對分查找及其算法實現》教學設計

湖北省巴東縣第一高級中學 劉少銀

一、教材學情分析

本次課是浙江版高中信息技術選修教材《算法與程序設計》第二章算法實例第四節查找中的一部分內容。由于教材體系不適合校本實際，我們在教學過程中對教材體系作了如下調整。

講授順序：第一章 算法和算法的表示、第三章 面向對象的程序設計的基本知識、第四章 VB程序設計初步、第二章算法實例，第五章 算法實例的程序實現穿插在相關內容教學中完成。

因此在前期教學中學生已經初步掌握了算法基礎及算法表示，VB程序設計初步等。本次課是讓學生掌握對分查找的思想及算法的實現。

二、教學目標

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

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

情感、態度與價值觀：感受信息技術與現實生活的關聯，激發對信息技術學科的求知欲，培養主動學習和使用信息技術的意識；養成科學的學習態度，不迷信書本、不迷信權威。

三、教學重難點

教學重點：對分查找的基本方法及注意事項；

教學難點：對分查找算法的實現。

四、教學策略

·以“猜數”游戲導入，引入對分查找的概念；

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

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

·采用自然評價、師生評價、生生評價等形式對學習進行過程性評價。

五、教學過程

1．游戲激趣，釋疑對分查找

（三個程序圖片）

（初始界面）（人工猜數界面）（程序猜數界面）

準備：幾張白紙，一支記號筆。啟動猜數程序。

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

同學：猜數游戲程序。

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

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

生：不神奇。

師：對，我也是這樣認為的。這個程序神奇的地方在它能幫助猜商品價格人在規定的時間內，根據主持人的提示準確地猜出商品的價格，而且猜中率100%，所以現在“幸運52”停播了，大家知道為什么嗎？

生：不知道。

師：就是因為我開發了這個程序呀！

生：（有的說信，有的抱著懷疑的態度不吭聲，也有說不信的）

師：有同學愿意上來試試嗎？

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

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

（程序找到正確的數）

師：神奇吧。

師：還有那位同學愿意試一下。

師：同樣，你還是先寫下要猜的數和范圍100～200，這次我們不讓大家看到他要猜的數，請大家幫忙記下程序每次出現的數字。

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

程序給出的數字是：

第一個數是：150

第二個數是：12

5第三個數是：137

第四個數是：1

31第五個數是：13

4最后是：13

2大家能看出什么規律了嗎？

生：看不出

師：單純從這幾個數當中是看不出什么規律，現在我們依次把這些數放到數軸上，再看一下，大家看能找出什么規律呢？

同學發言??

師：大家認為他說的怎樣？為什么不鼓掌呀！

師：對，正如剛才的同學說的那樣，程序是在給定范圍內依次找中點方法來找到我們要找的最終數值，這就是我們今天要討論的一種新的查找方法：對分查找。

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

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

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

生：能。

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

同學：不能。

師：對，這就是對分查找方法的一個特征，或稱為條件。因為我們是根據數據的大小找到它在數列中的位置。

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

2．分析實例，實現對分查找算法

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

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

生：??（有點茫然）

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

生：int。

師：對。即int（137．5），結果是多少？

生：137。

師：所以我們查找i到j范圍內的中點值的表達式應該為：m=int（（i+j）/2）。

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

師：請同學們根據算法逐步求精的原則在下面畫出流程圖。

（展示如下流程圖，然后請同學完成完善對分查找的算法流程圖）

流程圖補充完善后的結果：

【設計意圖】通過對程序給出中間數的分析，幫助學生理解對分查找算法實現的方法，為學生順利完成對分查找算法流程圖給予理論與實踐上的支持。

3．推出特例，完善對分查找算法

師：同學們，剛才我們完成的對分查找的流程圖；下面請同學們用剛才的查找方法分析一下在199至200范圍內要找200這個數，能找到嗎？為什么？如何解決這個問題？

（將教室內學生按座位分成若干組，進行討論。每個組推選一名小 組長，完成后作小組發言）

??

（每一小組完成發言后，老師或點評，或讓學生點評）

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

（在同學們的發言聲中，修改完善流程圖）

修改后的流程圖如下：

【設計意圖】給出特例，讓學生相互討論、互助學習，歸納總結出上述流程圖中出現問題的癥結所在，并給出正確的流程圖；由此可讓學生體驗到科學探究的方法，從而培養學生的科學態度與探索精神。

六、課后作業

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

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

（提示：認真閱讀教材P40至P43內容，并分析教材中所給算法的邏輯錯誤）

作業提交方式：電子郵件（校內、校外均可）

郵件名稱：登分號+姓名+論文題目

作業提交地址：bdxyz@qq.com

【設計意圖】作業（1）擴充課堂內容，豐富學生知識面，豐富學生分別學習內容；作業（2）通過兩個流程圖之間差異性比較，引導學生判別書本上所給出流程圖的邏輯錯誤，從而培養學生：1．科學的學習態度和精神，不迷信教材、不迷信權威；2．運用論文等形式來表達自己觀點；3．通過學生自己的分析、探索，找出教材中的錯誤。

七、教學反思

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