Search
搜尋法
搜尋(Search)
搜尋就是在一堆資料中找出所要之特定資料。搜尋之主要核心動作為「比較」動作，必需透過比較才有辦法判斷是否尋找到特定資料。當資料量少時很容易，當資料量龐大時，如何快速搜尋為一重要課題。
一般電腦檔案都是一群結構記錄之集合(如上一單元之成績結構)。為了排序與搜尋，至少會設定其中一個欄位為資料之鍵值(key)。透過鍵值將資料排列順序，稱為排序。透過鍵值找到特定資料，稱為搜尋(search)。一般資料搜尋有下列分類：
依資料量大小
1. 內部搜尋：欲搜尋之資料較少，可直接載入記憶體中，進行搜尋動作。
2. 外部搜尋：欲搜尋之資料較多，無法一次載入記憶體進行搜尋動作。需使用外部輔助記憶體分批處理。
依搜尋時資料表格是否異動
1. 靜態搜尋：搜尋過程中，資料表格不會有任何異動(如：新增、刪除或更新)。例如：查閱紙本字典、電話簿。
2. 動態搜尋：搜尋過程中，資料表格會經常異動。
一般搜尋常見之演算法有，「循序搜尋」、「二分搜尋」、「二元樹搜尋」、「雜湊搜尋」。
循序搜尋法(Sequential Search)
【定義】 從第一個資料開始取出，依序一一與「目標資料」相互比較，直到找到所要元素或所有資料均尋找完為止，此方法稱「循序搜尋」。
【優點】(1) 程式容易撰寫。
(2) 資料不須事先排序(Sorting)。
【缺點】 搜尋效率比較差(平均次數=(N+1)/2)，不管是否有排序，每次都必須要從頭到尾找一次。
【時間複雜度】
(1) 如果資料沒有重覆，找到資料就可終止，否則要找到資料結束。N筆資料，在最差之情況下，需作N次比較，O(N)。
(2) 在平均狀況下(假設資料出現與分佈之機率相等)需(N+1)/2次比較，所以平均時間與最差時間為O(N)，最好為O(1)=1次。
【演算法】
int sequential_search(int list[], int n, int key)
{
int i;
for (i = 0; i < n; i++)
{
if (list[i] == key) return i+1;
//比對陣列內的資料是否等於欲搜尋的條件
//若找到符合條件的資料，就傳回其索引
}
return(-1);
//若找不到符合條件的資料，就傳回 -1
}
二分搜尋法(Binary Search)
【定義】如果資料已先排序過，則可使用二分法來進行搜尋。二分法是將資料分成兩部份，再將鍵值與中間值比較，如鍵值相等則找到，小於再比前半段，大於再比後半段。如此，分段比較至找到或無資料為止。
【優點】搜尋效率佳(平均次數=Log2N)。
【缺點】 (1) 資料必需事先排序。
(2) 檔案資料必需使是可直接存取或隨機檔。
【時間複雜度】因為每次比較都會比上一次少一半之資料，因此最多只需要比較 ，。
【演算法】
Searchtime = 0; //搜尋次數初值設定為
Middle = (int)((Low + High)/2); //搜尋中間值
do
{
Searchtime = Searchtime + 1;
if (Temp[Middle] == Key) //找到資料
{
printf("該數字是排在第 %d 個順位",Middle);
//顯示資料位置
printf("一共搜尋 %d 次",Searchtime);
//顯示搜尋次數
break; //跳出迴圈
}
else if(Temp[Middle] < Key)
Low = Middle + 1; //改變左半部
else High = Middle - 1; //改變右半部
Middle = (int)((Low + High) / 2); //改變中間值
}
while(Low <= High);
二元樹搜尋法(Tree Search)
【定義】二元數是先將資料列建立為一棵二元搜尋樹，樹中每節點皆不小於左子樹(葉)，也不大於右子樹(葉)，也就是 左子樹的值≦樹根值≦右子樹的值。
【優點】 (1) 插入與刪除時，只需改變指標。
(2) 二元樹效率較高(介於循序法與二分法間)。
【缺點】 (1) 有左、右兩指標，需較大記憶體空間。
(2) 資料必須事先排序。
【時間複雜度】平均與最差時間為O(N)
內插搜尋法(Interpolation Search)
【定義】內插搜尋法是二分搜尋法之改良版。是依照資料位置分佈，運用公式預測資料所在位置，再以二分法方式逼近。內插之預測公式為：
【優點】資料分佈平均時，搜尋速度極快。
【缺點】 (1) 需計算預測公式。
(2) 資料必須事先排序。
【時間複雜度】取決於資料分部情形，平均而言優於Log2N。
【演算法】
int intsrch(int A[], int find)
{
int low, mid, high,Searchtime;
low = 0;
high = MAX - 1;
Searchtime = 0; //搜尋次數初值設定為
while(low <= high)
{
mid = (high-low)* (find-A[low])/(A[high]-A[low])+ low;
Searchtime = Searchtime + 1;
if(mid < low || mid > high) return -1;
if(find < A[mid]) high = mid - 1;
else if(find > A[mid])
low = mid + 1;
else
{
printf("一共搜尋 %d 次, ",Searchtime);//顯示搜尋次數
return mid;
}
}
return -1;
}
雜湊搜尋法(Hashing Search)
存取資料時，並不依資料順序存取，是應用資料中某欄位之值代入事先設計好之函數(雜湊函數)，計算資料存放之位置。這種方式稱雜湊法(Hashing)。
【定義】將資料按照某特定法則轉換為資料儲存位置，應用時是以資料鍵值(key value)轉換。
【優點】 (1) 搜尋速度最快。
(2) 資料不須是先排序。
(3) 在沒發生碰撞(collision)與溢位(overflow)之情況下，只需一次即可讀取。
(4) 搜尋速度與資料量大小無關。
(5) 保密性高，若不知雜湊函術，無法取得資料。
【缺點】 (1) 浪費空間(因有溢位資料區)，並且儲存空間的利用率比循序檔差。
(2) 有碰撞問題，當資料檔記錄到一定量時會嚴重影響處理速度存取速度。
(3) 程式設計比較複雜。
(4) 大量資料無效率。
(5) 不適合循序型煤體，如磁帶。
【演算法】主要依雜湊函數之計算、碰撞與溢位為考量依據。以下簡單討論幾種雜湊函數與溢位處理方法。
