1.基本概念
查找——在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)元素的過程稱為查找。
查找表（查找結(jié)構(gòu)）——用于查找的數(shù)據(jù)集合稱為查找表，它由同一類型的數(shù)據(jù)元素（或記錄）組成。
關(guān)鍵字——數(shù)據(jù)元素中唯一標(biāo)識該元素的某個數(shù)據(jù)項的值，使用基于關(guān)鍵字的查找，查找結(jié)果應(yīng)該是唯一的。
1.常見操作
- 1.查找符合條件的數(shù)據(jù)元素（靜態(tài)查找表）
- 2.插入，刪除某個數(shù)據(jù)元素（動態(tài)查找表）
2.查找算法的評價指標(biāo)
- 1.查找長度——在查找運算中，需要對比關(guān)鍵字的次數(shù)稱為查找長度。
- 2.平均查找長度（ASL，Average Search Length）——所有查找過程進(jìn)行關(guān)鍵字的比較次數(shù)的平均值。
ASL = ∑PiCi（i由1->n）
n為數(shù)據(jù)元素個數(shù)，P為查找第i個元素的概率，C為查找第i個元素的查找長度。
注：通常認(rèn)為查找任何一個元素的概率都相同
2.順序查找
定義：順序查找又叫線性查找，通常用于線性表（順序或者鏈?zhǔn)剑?/strong>
思想：從頭到尾依次查找（順序或者逆序）
代碼實現(xiàn)：
typedef struct{ // 查找表的數(shù)據(jù)結(jié)構(gòu)（順序表）
int *arr; // 動態(tài)數(shù)組基址
int length; // 表的長度
}SequenceTable;
// 順序查找
int Search_Seq(SequenceTable ST, int data){
int i;
for(i=0; i < ST.length && ST.arr[i] != data; ++i);
// 查找成功，則返回元素下標(biāo)；查找失敗，則返回-1
return i==ST.length ? -1 : i;
}
3.折半查找
定義：折半查找也稱二分查找，僅適用于有序的順序表
注：順序表具有隨機訪問的特性，鏈表沒有
代碼實現(xiàn)：
typedef struct{ // 查找表的數(shù)據(jù)結(jié)構(gòu)（順序表）
int *arr; // 動態(tài)數(shù)組基址
int length; // 表的長度
}SequenceTable;
// 折半查找(二分查找)
int Binary_Search(SequenceTable ST, int data){
int low = 0;
int high = ST.length-1;
int mid;
while(low <= high){
mid = (low + high)/2; // 取中間位置
if(ST.arr[mid] == data){
return mid; // 查找成功則返回所在位置
}else if(ST.arr[mid] > key){
high = mid - 1; // 在前半部分繼續(xù)查找
}else{
low = mid + 1; // 在后半部分繼續(xù)查找
}
return -1; // 查找失敗，返回-1
}
}
折半查找判定樹的構(gòu)造:
- 1.如果當(dāng)前l(fā)ow和high之間有奇數(shù)個元素，則mid分隔后，左右倆部分元素個數(shù)相等。
- 2.如果當(dāng)前l(fā)ow和high之間有偶數(shù)個元素，則mid分隔后，左半部分比右半部分少一個元素。
- 3.折半查找的判定樹中，若mid=┕(low+high)/2┙，則對于任何一個結(jié)點，必有：
右子樹結(jié)點數(shù) - 左子樹結(jié)點數(shù) = 0或1 - 4.折半查找的判定樹一定是平衡二叉樹，且只有最下面一層是不滿的，因此，元素個數(shù)為n時樹高h(yuǎn) = ┌log2(n + 1)┐
- 5.判定樹的結(jié)點關(guān)鍵字為
左 < 中 < 右，滿足二叉排序樹的定義，且失敗結(jié)點為（n+1）個 = 成功結(jié)點的空鏈域數(shù)量
4.分快查找
"索引表"中保存每個分快的最大關(guān)鍵字和分塊的存儲區(qū)間。
特點：塊內(nèi)無序，塊間有序
思想：分塊查找，又稱索引順序查找，算法如下：
- 1.在索引表中確定待查記錄所屬的分塊(可順序，可二分)
- 2.在快內(nèi)順序查找
查找效率分析（ASL）
問題：假設(shè)，長度為n的查找表均勻的分為b快，每塊s個元素。
解決：設(shè)索引查找和快內(nèi)查找的平均查找長度分別為LI、LS，則分塊查找的平均查找長度為ASL = LI+LS
- 使用順序查找查索引表，則LI=(1+2+...+b)/b = (b+1)/2，LS=(1+2+...+s)/s = (s+1)/2
則ASL= (b+1)/2+(s+1)/2 = (s2+2s+n)/2s，當(dāng)s=n(1/2)時，ASL取最小值=n(1/2) + 1
