搜尋資料結構 Search Structures

學習目標 在學習本章之後，讀者們要能夠瞭解： 搜尋的定義。 搜尋的種類及不同搜尋的資料結構及演算法。 電腦程式如何處理資料的搜尋。

搜尋 主要目的是從一組資料中尋找符合某種條件的資料，若是以資料的值來搜尋，可以把這個值當作搜尋鍵 (Search key)，根據搜尋鍵找到的是所有和搜尋鍵等值的資料。 電腦搜尋資料的優點是快速 當資料量很龐大時，如何快速搜尋到資料是本章所要探討的 一般電腦檔案是記錄的集合，每一筆記錄包含許多欄位，其中必須至少有一個欄位可當作關鍵值（key），從資料檔案中找出滿足某些關鍵值的記錄之動作稱之為搜尋（search）

搜尋的分類 在最短時間內有效的找到所需資料，是一個相當重要的課題 影響插搜尋時間長短的主要因素包括有演算法、資料儲存的方式及結構

內部搜尋與外部搜尋 內部搜尋： 外部搜尋： 欲找尋的資料或檔案較小，可以直接全部載入記憶體中來進行搜尋的動作。 若要找尋的資料數目很大，無法一次將全部內容置於主記憶體內，而需使用到外部的輔助記憶體來分次處理。

靜態搜尋及動態搜尋 靜態搜尋(Static Search) ： 動態搜尋(Dynamic Search) ： 在搜尋過程中，資料不會有增加、刪除或更新等行為。例如符號表的搜尋。 動態搜尋(Dynamic Search) ： 在搜尋過程中，資料會經常有增加、刪除或更新等行為。

循序搜尋法 Sequential search

定義 循序搜尋 (Sequential search)，又稱為線性搜尋(Linear Searching)，是最單純亦是最基本的搜尋方式 不需事先將被搜尋的檔案記錄按其鍵值排序，只需依照資料儲存的順序，逐一比較資料值是否與指定的值相等，若找到則傳回陣列的索引值，否則傳回0。

演算法 ＝＞虛擬碼 //n指a[ ]中的元素個數，key為欲比對的資料// procedure seqsch(int a[ ], int n, int key) { index i ; for (a [ ]的第一個元素至最後一個元素) if(key = = a [i]) 顯示找到的訊息並跳出迴圈; } if (到最後的元素仍找不到) 顯示找不到的訊息;

＝＞C語言程式碼 int seqsch(int a[ ], int n, int key) { int i = 0; a[n] = key; while (a[i] != key) i + +; if (i < n) printf(“%d 在陣列中的第 %d 筆.\n”,key,i+1) ; return(i); else printf(“找不到資料!!\n”) ; return(-1); }

＝＞時間複雜度分析 最差狀況指的是必須搜尋整個陣列，即資料並未出現在陣列中，在此情況下演算法必須做n次比較。

程式實作 #include <stdio.h> void main ( ) { int data [10] = {75, 33, 98, 44, 56, 24, 65, 48, 83, 12} int i, input ; printf ( “\n<< Squential search >>\n”) ; printf ( “\nData: “ ) ; for ( i= 0; i < 10; i + +) { printf ( “%d “, data [i] ); puts(“ “); printf ( “\nPlease enter a number from data: “ ) ; scanf ( “%d”, &input); printf ( “\nSearch…..\n” ) ;

for ( i = 0; i < 10; i ++) { printf ( “nData when searching %2d time(s) is %d !”, i+1, data[i]); if ( input = = data [i] ) break ; } if ( i = = 10 ) printf ( “\n\nSorry, %d not found ! “, input ) ; else printf ( “\n\nSorry, %d is the %dth record in data! “, input, i+1 ) ;

二分搜尋法 Binary Search

定義 假如資料本身是經過排序的，在搜尋時可以利用二分的方法，每次都把陣列分成兩半，然後從其中的一半繼續搜尋，這種方法叫做「二分搜尋」(Binary search)

二分搜尋的演算法

演算法則 檔案中的資料須按鍵值排序，並找出檔案中間位罝的鍵值Km用來作比較，其中m = (1+u)/2，1及u表示資料的開始及結束位址。 搜尋方式分下面三種情形進行： Key < Km：則表示欲尋找的資料在檔案的前半部。 Key = Km：則表示搜尋成功，傳回搜尋到的位置。 Key > Km：則表示欲尋找的資料在檔案的後半部。 重新調整1及u，並重複上述步驟，直到搜尋成功或資料已全部搜尋完畢為止。

演算法 ＝＞虛擬程式碼 int binsch(int a[ ], int low, int high, int key) { int mid; if (low <= high mid = (low+high)/2; if (a[mid] = = key) return(mid); else if (a [mid] > key) return(binsch(a,low,mid – 1,key)); else return return(binsch(a,low,mid + 1,key)); } else return(-1);

＝＞C語言程式碼 int binsch(int a[ ], int low, int high, int key) { int mid; if (low <= high mid = (low+high)/2; if (a[mid] = = key) return(mid); else if (a [mid] > key) return(binsch(a,low,mid – 1,key)); else return return(binsch(a,low,mid + 1,key)); } else return(-1);

＝＞時間複雜度分析 【分析】 由於二分搜尋每一次搜尋都要比上一次少一半的範圍，所以要找出資料的位置，最多只需要比較[log2n] +1或[log2(n＋１)]次。

程式實作 #include <stdio.h> void main ( ) { int data [10] = {12, 24, 29, 38, 44, 57, 64, 75 ,82, 98} int i, l = 1, u = 10, m, cnt = 0, input, ok = 0 ; printf ( “\n<< Binary search >>\n”) ; printf ( “\nSorted Data: “ ) ;

for ( i= 0; i < 10; i + +) printf ( “%d “, data [i] ); puts(“ “); printf ( “\nPlease enter a number from data: “ ) ; scanf ( “%d”, &input); printf ( “\nSearch…..\n” ) ; m = (1 +u)/2 while ( l <= n && ok = = 0 ) { printf ( “nData when searching %2d time(s) is %d !”, ++cnt, data[m]); if (data [i] > input ) u = m – 1 print ( “ --->Choice number is smaller than %d, data[m] ) ; } else

if ( data [m] < input ) { l = m +1; printf ( “--->Choice number is bigger than %d”, data [m] ); } else printf ( “\n\nfound, %d is the %dth record in data ! “, input, m) ; ok = 1; m = (1+u)/2 if ( ok = = 0) printf ( “\n\nSorry, %d not found ! “, input ) ;

內插式搜尋法

定義 內插式搜尋法是二分搜尋法的改良，它能更準確地預測資料位置所在，若假設所有資料是平均分佈在整個陣列之中，也就是每一筆資料值的差距是很接近的。

資料key位置的合理假設為： 或 其中key是要尋找之鍵值 Max(high)和Min(low)分別是剩餘待尋找之記錄中值最小和最大者。 Middle = Min + ( target - List(Min) ) * ( Max - Min ) / ( List(Max) - List(Min) 或 Middle = low + ( key – a [low] )* ( high - low ) / ( a[high] – a[low] ) 其中key是要尋找之鍵值 Max(high)和Min(low)分別是剩餘待尋找之記錄中值最小和最大者。

插補搜尋之步驟 先將記錄按鍵值不遞減之順序加以排序並編號，編號為1,2,3,…,N。 令a = 1，b = N。 令m = Min +。 若key < keym，且List(Max) ≠ m - 1，則令List(Max) = m - 1。 若key = keym，則成功。 若key > keym，且List(Min) ≠ m + 1，則令List(Min) = m + 1。

演算法 ＝＞虛擬程式碼 int intpsch(int a[ ], int n, int key) { int mid, high, low ; high = n – 1 ; low = 0 ; while (low <= high)

{ mid = low + (high - low)*(key –a [low] ) / (a [high ] – a[low]); if (a[mid] = = key) return(mid); else if (a [mid] > key) high = mid –1 ; else low = mid +1 ; } return(-1);

＝＞C語言程式碼 int intpsch(int a[ ], int n, int key) { int mid, high, low ; high = n – 1 ; low = 0 ; while (low <= high) mid = low + (high - low)*(key –a [low] ) / (a [high ] – a[low]);

＝＞時間複雜度分析 if (a[mid] = = key) return(mid); else if (a [mid] > key) high = mid –1 ; else low = mid +1 ; } return(-1); ＝＞時間複雜度分析 【分析】 一般而言，內插式搜尋法優於循序法，但與其他方法的優劣勝負則完全決定於鍵值分佈平均與否，通常N > 500且鍵值分佈均勻時會優於二元搜尋法。

程式實作 #include <stdio.h> void main ( ) { int data [10] = {12, 24, 29, 38, 44, 57, 64, 75 ,82, 98} int i, l = 1, n = 10, m, cnt = 0, input, ok = 0 ; printf ( “\n<< Interpolation search >>\n”) ; printf ( “\nSorted Data: “ ) ;

for ( i= 0; i < 10; i + +) printf ( “%d “, data [i] ); puts(“ “); printf ( “\nPlease enter a number from data: “ ) ; scanf ( “%d”, &input); printf ( “\nSearch…..\n” ) ; m = (1 +u)/2

while ( (n-l) > 1 && ok = = 0 ) { m = l + ( input – data [l] * (n – l -1) / ( data [n] – data [l] + 1; if ( m > n | | m < l ) break ; printf ( “nData when searching %2d time(s) is %d !”, ++cnt, data[m]);

if ( data [m] > input ) { n = m ; printf ( “ --->Choice number is smaller than %d, data[m] ) ; } else if ( data [m] < input ) l = m ; printf ( “--->Choice number is bigger than %d”, data [m] );

else { printf ( “\n\nfound, %d is the %dth record in data ! “, input, m) ; ok = 1; } if ( ok = = 0) printf ( “\n\nSorry, %d not found ! “, input ) ;