搜尋就是在一堆資料中找出所要之特定資料。搜尋之主要核心動作為「比較」動作，必需透過比較才有辦法判斷是否尋找到特定資料。當資料量少時很容易，當資料量龐大時，如何快速搜尋為一重要課題。
一般電腦檔案都是一群結構記錄之集合(如上一單元之成績結構)。為了排序與搜尋，至少會設定其中一個欄位為資料之鍵值(key)。透過鍵值將資料排列順序，稱為排序。透過鍵值找到特定資料，稱為搜尋(search)。一般資料搜尋有下列分類：
1. 內部搜尋：欲搜尋之資料較少，可直接載入記憶體中，進行搜尋動作。
2. 外部搜尋：欲搜尋之資料較多，無法一次載入記憶體進行搜尋動作。需使用外部輔助記憶體分批處理。
1. 靜態搜尋：搜尋過程中，資料表格不會有任何異動(如：新增、刪除或更新)。例如：查閱紙本字典、電話簿。
2. 動態搜尋：搜尋過程中，資料表格會經常異動。
一般搜尋常見之演算法有，「循序搜尋」、「二分搜尋」、「二元樹搜尋」、「雜湊搜尋」。
【定義】 從第一個資料開始取出，依序一一與「目標資料」相互比較，直到找到所要元素或所有資料均尋找完為止，此方法稱「循序搜尋」。
【優點】(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
}
【定義】如果資料已先排序過，則可使用二分法來進行搜尋。二分法是將資料分成兩部份，再將鍵值與中間值比較，如鍵值相等則找到，小於再比前半段，大於再比後半段。如此，分段比較至找到或無資料為止。
【優點】搜尋效率佳(平均次數=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);
【定義】二元數是先將資料列建立為一棵二元搜尋樹，樹中每節點皆不小於左子樹(葉)，也不大於右子樹(葉)，也就是 左子樹的值≦樹根值≦右子樹的值。
【優點】 (1) 插入與刪除時，只需改變指標。
(2) 二元樹效率較高(介於循序法與二分法間)。
【缺點】 (1) 有左、右兩指標，需較大記憶體空間。
(2) 資料必須事先排序。
【時間複雜度】平均與最差時間為O(N)
【定義】內插搜尋法是二分搜尋法之改良版。是依照資料位置分佈，運用公式預測資料所在位置，再以二分法方式逼近。內插之預測公式為：
【優點】資料分佈平均時，搜尋速度極快。
【缺點】 (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)。
【定義】將資料按照某特定法則轉換為資料儲存位置，應用時是以資料鍵值(key value)轉換。
【優點】 (1) 搜尋速度最快。
(2) 資料不須是先排序。
(3) 在沒發生碰撞(collision)與溢位(overflow)之情況下，只需一次即可讀取。
(4) 搜尋速度與資料量大小無關。
(5) 保密性高，若不知雜湊函術，無法取得資料。
【缺點】 (1) 浪費空間(因有溢位資料區)，並且儲存空間的利用率比循序檔差。
(2) 有碰撞問題，當資料檔記錄到一定量時會嚴重影響處理速度存取速度。
(3) 程式設計比較複雜。
(4) 大量資料無效率。
(5) 不適合循序型煤體，如磁帶。
【演算法】主要依雜湊函數之計算、碰撞與溢位為考量依據。以下簡單討論幾種雜湊函數與溢位處理方法。
雜湊函數之相關名詞說明：
【桶，bucket】雜湊表中儲存資料的位置，每一位置給定一個唯一的位址，此位址稱為bucket address。
【槽，slot】每一個位置(桶)有多個資料儲存區，每一儲存區稱為槽(slot)。每一槽可以容納一筆記錄。
【碰撞，collision】當不同之鍵值經雜湊函數計算後，落在相同的位置(bucket address)，稱之為碰撞。
【溢位，overflow】如有一鍵值經雜湊函數計算後，相對應之位置(桶,bucket)已裝滿，就稱為溢位。
此方法，鍵值平方後，取出中間某些位元當作資料儲存的位址。
【範例】假設有一鍵值k=510324。若儲存空間(桶數目)為104，也就是取四位數(0000~9999)。則雜湊函數h(k)
h(k)=k2取中間四位數=260430584976取中間四位數=3058
此方法，是將鍵值分為數段，除最後一段外，其餘各段皆等長(等於儲存空間，桶數目)。然後，將各段相加，就可得所對應之位址。相加方式有兩種：
【位移折疊，shifting folding】將各段直接相加。
範例：鍵值123203241112205
à123,203,241,112,205à(+)à884 (hash address)
【邊界折疊，folding at the boundaries】將奇數段或偶數段反轉後相加。
範例：鍵值123203241112205
à123,203,241,112,205à(偶反轉)
à123,302,241,211,205à1082(hash address)
此方法運用MOD運算，將鍵值X除以某一數值 M，取其餘數當作X的位址。這位址介於0~M-1間。一般M建議使用質數效果較佳(不會有因數消去之問題)。
h(X)= X mod M
【範例】假設有一鍵值數列{X}={15,29,52,100,200}。以除數M=13，則依h(X)= X mod M，建立之雜湊表為：
|
X |
X mod 13 |
位址 |
資料鍵值 |
|
15 |
0 |
52 |
|
|
29 |
1 |
|
|
|
52 |
2 |
15 |
|
|
100 |
3 |
29 |
|
|
200 |
4 |
|
|
|
|
5 |
200 |
|
|
|
6 |
|
|
|
|
7 |
|
|
|
|
8 |
|
|
|
|
9 |
100 |
|
|
|
10 |
|
|
|
|
11 |
|
|
|
|
12 |
|
此方法需先對資料鍵值之分佈情形詳細分析再設計雜湊函數，數字分析法有兩種：
【目視數字分析法】利用目視法，將鍵值各位數的分佈不均的數字刪除，其餘保留為雜湊位址(hash address)。
【統計數字分析法】運用統計方法分析鍵值各位數的分佈情形，求出雜湊位址(hash address)。
一般常見方法有：線性探測法(linear
probing)、鏈結串列(chaining)、平方探測(quadratic probing)、再雜湊(rehashing)。
又稱線性開放定址(linear
open addressing)。將雜湊位址視為環狀空間，當溢位發生時，以線性方式找下一個空的儲存空間將資料存入。
【優點】容易使用。
【缺點】易產生「主要群集」問題，也就是一群資料有相近之hashing address之問題，長時間執行會增加平均搜尋時間。
將碰撞之資料(data)放到溢位資料區(overflow data area)，並用指標連結。
【優點】容易使用。
【缺點】需求溢位資料區(overflow data area)，需使用指標函數。
此方法改善線性探測法之「主要群集」問題，可避免相近之鍵值聚在一起。當h(X)位址發生溢位時，下一次探測位址為
(h(X)+i2) mod b 與 (h(X)-i2) mod b
其中，1≦i≦(b-1)/2，b為可表示為4j+3型式之質數。
事先設計好一套雜湊函數 h1、h2、h3、…、hm，當溢位時先使用h1，若再發生溢位則依次使用h2、h3、…、hm，至沒溢位發生或沒雜湊函數。