文章目錄
- 順序查找
- 應用範圍
- 資料元素類型定義
- 順序查找算法
- 改進後的順序查找算法
- 順序查找時間效率分析
- 順序查找的性能分析
- 順序查找優缺點讨論
- 折半查找（二分或對分查找）
- 折半查找算法（非遞歸算法）
- 折半查找——遞歸算法
- 折半查找性能分析
- 判定樹
- 折半查找優缺點
- 分塊查找（索引順序查找）
- 分塊查找過程
- 分塊查找性能分析
- 分塊查找優缺點
- 三種查找方法的比較
順序查找
應用範圍
- 順序表或線性連結清單表示的靜态查找表。
- 表内元素之間無序。
資料元素類型定義
// 資料元素類型定義
typedef struct {
KeyType key; // 關鍵字域
InfoType otherinfo; // 其他域
} ElemType;
// 順序表的定義
typedef struct{
ElemType *R; // 存儲空間基位址
int length; // 目前長度
}SSTable; // Sequential Search Table
SSTable ST; // 定義順序表ST 順序查找算法
在順序表ST中查找值為key的資料元素（從最後一個元素開始比較）。
int Search_Seq(SSTable ST, KeyType key){
// 若成功傳回其位置資訊，否則傳回0
for(i=ST.length;i>=1;--i)
if(ST.R[i].key==key) return i;
return 0;
} 改進後的順序查找算法
把待查關鍵字key存入表頭（哨兵、監視哨），可免去查找過程中每一步都要檢測是否查找完畢，加快速度。
int Search_Seq(SSTable ST,KeyType key)
{ // 在順序表 ST 中順序查找其關鍵字等于 key 的資料元素。若找到，則函數值為該元素在表中的位置，否則為 0
ST.R[O].key=key; // ＂哨兵”
for(i=ST.length;ST.R[i].key!=key;--i); // 從後往前找
return i;
} 當ST.length較大時，此改進能使進行一次查找所需的平均時間幾乎減少一半。
順序查找時間效率分析
比較次數與key位置有關：
- 查找第 i 個元素，需要比較n - i + 1次。
- 查找失敗，需比較n + 1次。
順序查找的性能分析
-
時間複雜度：O(n)
查找成功時的平均查找長度，設表中各記錄查找機率相等
ASLs(n) = (1+2+…+n) / n = (n+1) / 2
- 空間複雜度：一個輔助空間——O(1)。
順序查找優缺點讨論
優點：算法簡單，邏輯次序無要求，且不同存儲結構均适用。
缺點：ASL太長，時間效率太低。
讨論：
1.記錄的查找機率不相等時如何提高查找效率？
查找表存儲記錄原則——按查找機率高低存儲：
（1）查找機率越高，比較次數越少；
（2）查找機率越低，比較次數較多。
2.記錄的查找機率無法測定時如何提高查找效率？
方法——按查找機率動态調整記錄順序：
（1）在每個記錄中設一個通路頻度域；
（2）始終保持記錄按非遞增有序的次序排列；
（3）每次查找後将剛查到的記錄直接移至表頭。
折半查找（二分或對分查找）
每次将待查記錄所在區間縮小一半。
折半查找算法（非遞歸算法）
- 設表長為n，low、high和mid分别指向待查元素所在區間的上屆、下屆和中點，key為給定的要查找的值：
- 初始時，令low=1，high=n，mid=(low+high) / 2
- 讓k與mid指向的記錄比較
- 若key == R[mid].key，查找成功
- 若key < R[mid].key，則high=mid - 1
- 若key > R[mid].key，則low=mid + 1
- 重複上述操作，直至low>high時，查找失敗。
int Search_Bin(SSTable ST,KeyType key)
{ // 在有序表ST 中折半查找其關鍵字等于key的資料元素。若找到， 則函數值為該元素在表中的位置， 否則為0
low= 1;high=ST.length; //置查找區間初值
while(low<=high)
{
mid=(low+high)/2;
if{key==ST.R[mid].key) return mid; // 找到待查元素
else if{key<ST.R[mid].key) high=mid-1; // 繼續在前一子表進行查找
else low=mid+1; // 繼續在後一子表進行查找
}
return 0; // 表中不存在待查元素
} 折半查找——遞歸算法
int Search_Bin(SSTable ST, keyType key, int low, int high){
if(low>high) return 0; // 差找不到時傳回0
mid=(low+high)/2;
if(key==ST.elem[mid].key) return mid;
else if(key<ST.elem[mid].key)
...... // 遞歸，在前半區間查找
else ...... // 遞歸，在後半區間進行查找
} 折半查找性能分析
判定樹
查找成功：
比較次數 = 路徑上的結點數。
比較次數 = 結點層數。
比較次數 ≤ 樹的深度 = log2n + 1
查找不成功：
比較次數 = 路徑上的内部結點數
比較次數 ≤ log2n + 1
折半查找優缺點
優點：效率比順序查找高。
缺點：隻适用于有序表，且限于順序存儲結構（對線性連結清單無效）。
分塊查找（索引順序查找）
1.将表分成幾塊，且表或者有序，或者分塊有序；若 i < j，則第 j 塊中所有記錄的關鍵字均大于第 i 塊中的最大關鍵字。
2.建立“索引表”（每個結點含有最大關鍵字域和指向本塊第一個結點的指針，且按關鍵字有序）。
分塊查找過程
先确定待查記錄所在塊（順序或折半查找），再在塊内查找（順序查找）。
分塊查找性能分析
查找效率：ASL = Lb + Lw
Lb：對索引表查找的ASL。
Lw：對塊内查找的ASL。
如上公式，當n=9，s=3時，ASLbs=3.5，而折半法為3.1，順序法為5。
分塊查找優缺點
優點：插入和删除比較容易，無需進行大量移動。
缺點：要增加一個索引表的存儲空間并對初始索引表進行排序運算。
适用情況：如果線性表既要快速查找又經常動态變化，則可采用分塊查找。
三種查找方法的比較
| 順序查找 | 折半查找 | 分塊查找 | |
| ASL | 最大 | 最小 | 中間 |
| 表結構 | 有序表、無序表 | 有序表 | 分塊有序 |
| 存儲結構 | 順序表、線性連結清單 |