查找的基本概念
- 查找表：由同一類型的資料元素（或記錄）構成的集合
- 靜态查找表：查找的同時對查找表不做修改操作（如插入和删除）
- 動态查找表：查找的同時對查找表具有修改操作
- 關鍵字：記錄中某個資料項的值，可用來識别一個記錄
- 主關鍵字：唯一辨別資料元素
- 次關鍵字：可以辨別若幹個資料元素
查找算法的評價名額
- 關鍵字的平均比較次數，也稱平均搜尋長度ASL(Average Search Length)
n：記錄的個數
pi：查找第i個記錄的機率 ( 通常認為pi =1/n )
ci：找到第i個記錄所需的比較次數
線性表的查找
順序查找
- 應用範圍：順序表或線性連結清單表示的靜态查找表表内元素之間無序
- 結構定義
typedef int KeyType; typedef int InfoOther; typedef struct{ KeyType key; // 主鍵 InfoOther other; // 次鍵 }ElemType; typedef struct{ ElemType* elem; // 基位址 int length; // 表長 }SSTable; - 順序查找值為key的元素
int Search_Seq(SSTable ST,KeyType key){ for (int i=1; i<= ST.length; i++) if (ST.elem[i].key == key) return i; return 0; } - 改進，加入“哨兵”
int Search_Seq(SSTable ST,KeyType key){ //若成功傳回其位置資訊，否則傳回0 ST.elem[0].key = key; for (int i=ST.length; ST.elem[i].key != key; i--); return i; }
順序查找的性能分析
- 空間複雜度：一個輔助空間
- 時間複雜度：
-
查找成功時的平均查找長度
設表中各記錄查找機率相等
- 查找不成功時的平均查找長度 ASLf =n+1
-
順序查找算法特點
- 算法簡單，對表結構無任何要求（順序和鍊式）
- n很大時查找效率較低
- 改進措施：非等機率查找時，可按照查找機率進行排序。
查找機率相等時，ASL相同；
查找機率不等時，如果從前向後查找，則按查找機率由大到小排列的有序表其ASL要比無序表ASL小
折半查找
若k==R[mid].key，查找成功
若k<R[mid].key，則high=mid-1
若k>R[mid].key，則low=mid+1
直至low>high時，查找失敗
- 設表長為n，low、high和mid分别指向待查元素所在區間的上界、下界和中點,k為給定值
- 初始時，令low=1,high=n,mid=(low+high)/2
- 讓k與mid指向的記錄比較
- 重複上述操作，直至low>high時，查找失敗
算法描述
/*-----------折半查找----------*/
// 非遞歸算法
// 适用于順序存儲
int Search_Bin(SSTable ST, KeyType key){
//若找到，則函數值為該元素在表中的位置，否則為0
int low = 1;
int high = ST.length;
while(low <= high){
int mid = (low + high) / 2;
if(key == ST.elem[mid].key) return mid;
else if(key < ST.elem[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;
int mid = (low + high) / 2;
if(key == ST.elem[mid].key) return mid;
else if(key < ST.elem[mid].key) Search_Bin(ST, key, low, mid-1);
else Search_Bin(ST, key, mid+1, high);
} 折半查找性能分析
- 查找成功時比較次數：為該結點在判定樹上的層次數，不超過樹的深度 d = log2 n + 1 （log向下取整）
- 查找不成功的過程就是走了一條從根結點到外部結點的路徑d或d-1。
- 查找過程：每次将待查記錄所在區間縮小一半，比順序查找效率高,時間複雜度O(log2 n)
- 适用條件：采用順序存儲結構的有序表，不宜用于鍊式結構
分塊查找（塊間有序，塊内無序）
- 分塊有序，即分成若幹子表，要求每個子表中的數值都比後一塊中數值小（但子表内部未必有序）
- 然後将各子表中的最大關鍵字構成一個索引表，表中還要包含每個子表的起始位址（即頭指針）。
- 分塊查找過程
- 對索引表使用折半查找法（因為索引表是有序表）
- 确定了待查關鍵字所在的子表後，在子表内采用順序查找法（因為各子表内部是無序表
分塊查找性能分析
- 查找效率：ASL = Lb + Lw
- Lb:：對索引表查找的ASL
- Lw：對塊内查找的ASL
- ASL(bs): = log2 (n/s+1)+s/2 （log2 n <= ASL(bs) <= n(n+1)/2）
- 例如，當n=9，s=3時，ASL(bs)=3.5, 而折半法為 3.1, 順序法為 5
分塊查找優缺點
- 優點：插入和删除比較容易，無需進行大量移動。
- 缺點：要增加一個索引表的存儲空間并對初始索引表進行排序運算。
- 适用情況：如果線性表既要快速查找又經常動态變化，則可采用分塊查找。