二分搜寻演算法

高中資訊科課程架構「資訊科技概論」必修2~4學分(生活領域)2學分必修：核心知識為主4學分必修：

核心知識＋應用軟體或/及基礎程式設計「資訊科學」選修0～6學分(非升學科目)基礎程式設計

(1～2學分)進階程式設計

(2學分)資訊科學與應用專題

(1～4學分)其它(可依各校課程特色開設，0～2學分)99總綱選修科目與學分數選修一、概論1.程式設計簡介

2.程式設計工具2～4二、基礎觀念1.常數與變數

2.基本輸入輸出3.運算式與指定敍述

4.內建函式※4～6三、流程控制1.選擇敘述

2.重複敘述8～14四、陣列1.一維陣列

2.多維陣列※2～8五、模組化程式設計※1.副程式※

2.程式庫※0～6基礎程式設計(選修1~2學分)進階程式設計(選修2學分)一、模組化程式設計1.副程式

2.程式庫6～10二、進階資料型態1.陣列

2.資料錄3.指標※8～12三、資料結構1.佇列2.堆疊3.鏈結串列4.樹狀結構※5.集合※10～12四、演算法1.排序演算法2.搜尋演算法10～12單元摘要

本主題旨在介紹常用的演算法，以及如何針對演算法進行效能分析。授課重點應強調演算法垂直式邏輯思考的精神，以及循序漸進的解題流程，並搭配日常生活實例進行教學。先備知識

1.必修科目「資訊科技概論」

2.選修科目「基礎程式設計」

課綱範圍

1.排序演算法

1-1排序演算法用途

1-2泡沫排序演算法

1-3選擇排序演算法

1-4快速排序演算法※

1-5排序演算法效能分析※2.搜尋演算法

2-1搜尋演算法用途

2-2循序搜尋演算法

2-3二分搜尋演算法

2-4搜尋演算法效能分析

約7HR約5HR學習目標

能分別說明各式常見排序演算法的功能，及其在程式設計中的使用時機。能說明並比較各式排序演算法的差異。能利用複雜度分析方法，分析各式排序演算法的效能。能分別說明各式常見搜尋演算法的功能，及其在程式設計中的使用時機。能說明並比較各式搜尋演算法的差異。能利用複雜度分析方法，分析各式搜尋演算法的效能。第一堂課：排序介紹一、排序介紹1.何謂排序(Sorting)？2.內部排序VS

外部排序3.直接移動VS

邏輯移動二、排序演算法分析1.穩定度2.時間複雜度VS空間複雜度

排序(Sorting)是指將一群資料，依照特定規則調整位置順序，使資料具有某種次序。目的在使資料隨著特定順序排列組合。如班級成績資料，可以使用每個學生的總成績、總平均、名次或座號順序等排列方式，將資料由大至小或是由小至大來排列。內部排序：排序的資料量小，可以完全在記憶體內進行排序。內部排序法有：泡沫排序法、選擇排序法、快速排序法等。外部排序：排序的資料量無法直接在記憶體內進行排序，而必須使用到輔助記憶體。外部排序法有：直接合併排序法、堆積合併排序法等。(※)直接移動VS邏輯移動「直接移動」是直接交換儲存資料的位置。

如圖示。「邏輯移動」並不會移動資料儲存位置，僅改變指向這些資料的輔助指標的值。

如圖示。排序穩定度

穩定排序(StableSort)是指資料在經過排序後，兩個相同鍵值的記錄仍然保持原來的次序。舉例說明：如下例中，8左的原始位置本來在8右的左邊(所謂8左及8右是指相同鍵值一個在左，一個在右。)，穩定排序後8左仍應在8右的左邊，不穩定排序則有可能8左會跑到8右的右邊去。

原始資料順序：

8左

69 8右 7穩定的排序： 6

78左

8右

9不穩定的排序：

6

78右

8左 9時間複雜度

VS空間複雜度時間複雜度(Timecomplexity)：

1.可分為最好情況(BestCase)、最壞情況(WorstCase)及

平均情況(AverageCase)。

2.最好情況就是資料已完成排序。例如：原本資料已經完成

遞增(由小至大)排序，如果再進行一次遞增排序所使用的

時間複雜度就是最好情況。

3.最壞情況是指每一鍵值均須重新排列。例如：原本為遞增

排序重新排序成為遞減(由大至小)，就是最壞情況。空間複雜度(Spacecomplexity)：

1.指演算法在執行過程所需付出的額外記憶體空間。

2.排序法所使用到的額外空間愈少，空間複雜度就愈佳。

3.例如泡沫排序法在排序過程中僅用到一個額外空間，在所

有的排序演算法中，這樣的空間複雜度就算是最佳情況。第二堂課：泡沫排序法介紹1.排序原理：

泡沫排序演算法，又稱為氣泡排序法或交換排序法。是由觀察水中氣泡大小會隨著水深高度壓力變化演進而成。泡沫排序法的比較方式是由第一個元素開始，比較2個相鄰元素大小，若大小順序有誤，則立即對調，對調後再進行下一個元素的比較。2.教師舉例：(以五筆隨機資料，用泡沫排序法表示演算法過程。)

例題：「26,5,37,1,61」。結果：「1,5,26,37,61」。3.學生練習：(可隨機挑選若干位同學，以座號上台操作演練。)例題：數列「23,36,5,14,9」(隨機挑選同學座號，各班可能不同。)若經由泡沫排序法由小到大的順序排序，過程及結果為何？隨機挑選若干張撲克牌，由學生(可分組進行)操作泡沫排序法由小到大，互相觀察排序過程。

第三堂課：泡沫排序法程式程式參考示例與練習：(重點解說)voidBubble_Sort(intn,int*Data){

/*N筆資料儲存於Data[0]….Data[n-1]中*/inti,j,temp;for(i=0;i<n-1;i++)

{for(j=0;j<n-i;j++)

{

if(Data[j+1]<Data[j])

{

temp=Data[j];Data[j]=Data[j+1];Data[j+1]=temp;

/*交換資料swap*/

}

}printf("第%d次排序後的結果:",i+1);ShowData(6,Data); /*列印每次排序後的資料*/

}}

第四堂課：選擇排序法介紹1.排序原理：

選擇排序法可使用兩種方式排序，一為在所有的資料中，當由大至小排序，則將最大值放入第一位置；若由小至大排序時，則將最大值放入位置末端。選擇排序法分析：

1.不是穩定排序法。

2.時間複雜度為O(n2)。

3.只需一個額外的空間，所以空間複雜度為最佳。

4.適用於資料量小或有部份資料已經過排序者。2.教師舉例：(同「26,5,37,1,61」例，用選擇排序法表示過程。)3.學生練習：(可隨機挑選若干位同學，以座號上台操作演練。)例題：隨機挑選同學座號，形成數列「33,17,6,24,9」，經由選擇排序法由小到大的順序排序，過程及結果為何？隨機挑選若干張撲克牌，由學生(可分組進行)操作選擇排序法由小到大，互相觀察排序過程。第五堂課：選擇排序法程式程式參考示例與練習：(重點解說)voidSelect_Sort(intn,int*Data){

/*N筆資料儲存於Data[0]...Data[n-1]中*/inti,j,k,temp;for(i=0;i<n-1;i++)

{

k=i; /*掃瞄n-1次*/for(j=i+1;j<n;j++)

if(Data[j]<Data[k])k=j; /*尋找最小鍵值資料*/if(i!=k) /*交換資料swap*/

{temp=Data[i];Data[i]=Data[k];Data[k]=temp;} /*使此次掃瞄的最小鍵值資料擺在最前面*/printf("第

%d次排序後的結果:",i+1);ShowData(n,Data);}}第六堂課：快速排序法介紹1.排序原理：

快速排序法又稱分割交換排序法，是目前公認最佳的排序法。假設有n筆記錄R1，R2，R3，…，Rn，其鍵值分別為k1，k2，k3，…，kn。快速排序法的步驟如下：

(1)取K為第一筆鍵值。

(2)由左向右找出一個鍵值Ki使得Ki>K。

(3)由右向左找出一個鍵值Kj使得Kj<K。

(4)若i<j則Ki與Kj交換，並繼續步驟(2)的執行。

(5)若i

j則將K與Kj交換，並以j為基準點將資料分為左右兩部份。

(6)以遞迴方式分別為左右兩半繼續分別進行排序，直至完成排序。快速排序法分析：

1.快速排序法不是穩定排序法。

2.時間複雜度：最快及平均為O(nlog2n)，最壞為O(n2)。

3.空間複雜度：最差情況為O(n)，最佳情況為O(log2n)。

4.快速排序法是平均執行時間最快的排序法。第六堂課：快速排序法介紹2.教師舉例：

可利用以上過程，將左半部與右半部分別排序，形成遞迴，至於排序過程如下：第七堂課：快速排序法程式程式參考示例與練習：(重點解說)

voidq_sort(int*data,intm,intn){intk,temp,i,j; /*分割元素*/

if(m<n) /*是否繼續分割*/

{i=m; /*分割的最左*/j=n+1; /*分割的最右*/k=data[m]; /*取第一個元素*/do

{do /*由左往右找*/

{ i++;}while(data[i]<k);do /*由右往左找*/

{j--;}while(data[j]>k);if(i<j) /*交換資料*/

{

temp=data[i];data[i]=data[j];data[j]=temp;

}

}while(i<j);

temp=data[m];data[m]=data[j];

data[j]=temp;

/*交換資料*/printf("過程輸出:");for(i=m;i<=n;i++) /*列印過程*/printf("%3d",data[i]);printf("\n");

q_sort(data,m,j-1);q_sort(data,j+1,n);/*快速排序遞迴呼叫*/

}}

第八堂課：搜尋介紹一、搜尋介紹1.何謂搜尋(Search)？

2.靜態搜尋

VS動態搜尋3.內部搜尋

VS外部搜尋二、常見的搜尋方法1.循序搜尋法。(適合未經排序整理的資料)2.二元搜尋法。(適合已經排序整理的資料)3.其他：如內插搜尋法、費氏搜尋法。(斟酌補充※)三、循序搜尋演算法介紹1.搜尋原理2.效能分析

第八堂課：搜尋介紹靜態搜尋

VS動態搜尋

1.靜態搜尋：指在搜尋過程中，該資料不會有增加、刪除、或更新等行為。例如符號表搜尋。

2.動態搜尋：指所搜尋的資料，在搜尋過程中會經常性增加、刪除、或更新。例如B-tree搜尋。內部搜尋

VS外部搜尋

1.內部搜尋：資料量較小的檔案，可以直接全部載入記憶體中進行搜尋。

2.外部搜尋：資料量大的檔案，無法一次載入記憶體處理，而需使用到輔助記憶體來分次處理。第八堂課：循序搜尋法介紹循序搜尋法：

1.又稱為線性搜尋法，是一種最簡單的搜尋法。

2.優點是資料在搜尋之前不需要作任何的前置處理或排

序，缺點為搜尋速度較慢。

3.因此在平均狀況下，循序搜尋法搜尋一筆資料大約需

要(n+1)/2的比較次數。循序搜尋法分析：

1.時間複雜度：如果資料沒有重覆，找到資料就可中止

搜尋的話，在最差狀況是未找到資料，需作n次比較，

時間複雜度為O(n)。

2.當資料量很大時，不適合使用循序搜尋法。但如果預

估所搜尋的資料在檔案前端則可以減少搜尋的時間。第九堂課：循序搜尋法程式程式參考示例與練習：(重點解說)intsearch(int*data,intn,intkey){

/*資料比對的部分*/inti;for(i=0;i<n;i++) /*循序比對資料*/if(data[i]==key)returni; /*找到傳回第i筆*/returnn;}

/*沒找到資料*/

第十堂課：二分搜尋法介紹二分搜尋法原理：

將已排序的資料分割成兩等份，再比較鍵值與中間值，如果鍵值小於中間值，可確定要找的資料在前半段，否則在後半部。如此分割數次直到找到或確定找不到(不存在)為止。二分法分析：

1.時間複雜度：因為每次搜尋都會比上一次少一半的範圍，

最多約只需要比較[log2n]+1，時間複雜度為O(log2n)。

2.二分法必須事先經過排序，且資料量必須能直接在記憶體

中執行。適合用於不需增刪的靜態資料。舉例說明：

學生練習：

隨機挑選若干張撲克牌，由學生(可分組進行)先操作排序法(演算法不拘)由小到大，再使用二分搜尋法找出指定的牌並互相觀察操作過程。第十堂課：二分搜尋法介紹舉例說明：

例如以下已排序數列2、3、5、8、9、11、12、16、18

，而所要搜尋值為11時：(1)首先跟第五個數值9比較：(2)因11＞9，故和後半部的中間值(第七個數值)12比較：(3)因11＜12，故和前半部的中間值(第六個數值)11比較：(4)因為11=11，表示搜尋完成，如果不相等則表示找