查找的基本概念

基本概念

查找：在數據集合中尋找滿足某種條件的數據元素的過程

查找表（查找結構）：用于查找的數據集合稱為查找表，它由同一類型的數據結構元素（或記錄）組成

關鍵字：唯一標識該元素的某個數據項的值，使用基于關鍵字的查找，查找結果應該是唯一的

對查找表的常見操作

①查找符合條件的數據元素

②插入、刪除某個數據元素

只需要進行操作①–靜態查找表–著需要關注查找速度

也要進行操作②–動態查找表–還需要關注插入、刪除操作是否方便實現

查找算法的評價指標

查找長度：查找運算中，需要對比關鍵字次數

平均查找長度（ASL）：查找過程中進行關鍵字比較次數的平均值

通常考慮查找成功、查找失敗兩種情況下的ASL

順序查找

算法思想

從頭到尾/從尾到頭依次查找

基本實現

typedef struct{ElemType *elem;int TableLen;
}SSTable;//順序查找
int Search_Seq(SSTable ST,ElemType key){int i;for(i = 0;i<ST.TableLen && ST.elem[i] != key;++i);return i==ST.TableLen?-1:i;
}

實現（哨兵）

typedef struct{ElemType *elem;int TableLen;
}SSTable;//順序查找
int Search_Seq(SSTable ST,ElemType key){ST.elem[0] = key;					//查找表中從1號位置開始存放數據，0號位置存放“哨兵”int i;for(i = ST.TableLen;ST.elem[i] != key;--i);return i;							//查找成功，返回元素下標；查找失敗，返回0
}

優點：無需判斷是否越界，執行效率更高（但是并沒有質的提升）

效率分析

查找成功：ASL=(n+1)/2 時間復雜度：O(n)

查找失敗：ASL=n+1 時間復雜度：O(n)

順序查找的優化（對有序表）

以查找表中元素遞增存放為例：

若查找到某個元素大于查找目標，則可判定為查找失敗（后面的元素都大于查找目標）

ASL(失敗) = (1+2+……+n+n)/n+1 = n/2+n/(n+1)

查找算法判定樹分析ASL

一個成功節點的查找層數 = 自身所在的層數

一個失敗節點的查找長度 = 其父節點所在的層數

默認情況下，各種成功情況或失敗情況都等概率發生

折半查找（考察頻率高）

算法思想

又稱“二分查找”，僅適用于有序的順序表

每次將查找范圍折半，逐步縮小查找區間，直到找到目標元素或查找區間為空。

前提：數據必須是有序的（通常是升序）。

取中間元素：

• 計算中間下標 mid = (low + high) // 2。

比較中間元素和目標值：

• 若 target == arr[mid]：查找成功。
• 若 target < arr[mid]：繼續在左半部分查找。
• 若 target > arr[mid]：繼續在右半部分查找。

重復步驟 2-3，直到找到目標或范圍為空（low > high）。

算法實現

typedef struct{ElemType *elem;int TableLen;
}SSTable;int Binary_Search(SSTable L,ElemType key){int low = 0,high = L.TableLen-1,mid;while(low<=high){mid = (low+high)/2;			//取中間位置if(L.elem[mid] == key)return mid;				//查找成功返回所在位置else if(L.elem[mid]<key)low = mid+1;			//從后半部分查找elsehigh = mid-1;			//從前半部分查找}return -1;
}

查找效率分析

例：

ASL（成功） = (1*1 + 2*2 + 3*4 + 4*4)/11 = 3

ASL（失敗） = (3*4+4*8)/12 = 11/3

查找判定樹的構造

如果當前low和high之間有奇數個元素，則mid分割后，左右兩部分元素個數相等

如果當前low和high之間有偶數個元素，則mid分割后，左半部分比右半部分少一個元素

折半查找的判定樹中，若mid = [(low+high)/2] 則對于任何一個結點，必有：右子樹個數-左子樹個數 = 0或1

折半查找的判定樹一定只有最下面一層是不滿的

h = [log2(n+1)]

判定樹結點關鍵字：左<中<右，滿足二叉排序樹的定義

失敗節點：n+1（等于成功結點的空鏈域數量）

折半查找的查找效率

樹高h = [log2(n+1)] 查找成功ASL ≤ h 查找失敗ASL ≤ h

時間復雜度O(log2n)

[!WARNING]

折半查找的速度一定比順序查找更快？

? 一般情況下，折半查找比順序查找表現優秀，但不是所有情況下折半查找都更快

若mid = (low+high)/2（向上取整） ？

左子樹結點數-右子樹結點數 = 0或1

分塊查找（手算模擬+平均查找長度）

分塊查找的算法思想

eg. 第一個區間：≤10 第二個區間：≤20 ……

“索引表”中保存每個分塊的最大關鍵字和存儲的區間

特點：塊內無序，塊間有序

typedef struct{ElemType maxValue;int low,high;
}Index;//順序表存儲實際元素
ElemType List[100];

算法過程：

①在索引表中確定待查記錄所屬的分塊（可順序、可折半）

②在塊內順序查找

用折半查找查索引

若索引表中不包含目標關鍵字，則折半查找索引表最終停在low>high，要在low所指的分塊中進行查找

low超出索引表的范圍時，查找失敗

查找效率分析（ASL）

共有14個元素可能被查找，各自被查找的概率為1/14

若索引表順序查找

7（2）、10（3）、13（3）……

若索引表折半查找（一般不考、計算量大）

30（4）?、27（2）?

查找失敗的情況（更復雜，一般不考）

【可能會考的情況】（順序查找，效率和最優分塊）

【拓展思考】

若查找表是“動態查找表”，更好的實現方式 – 使用鏈式存儲

（否則在目標關鍵字插入時，需要大量元素的移動）