C++重識(shí)搜索算法

「搜索算法 searching algorithm」用于在數(shù)據(jù)結(jié)構(gòu)（例如數(shù)組、鏈表、樹或圖）中搜索一個(gè)或一組滿足特定條件的元素。

搜索算法可根據(jù)實(shí)現(xiàn)思路分為以下兩類。

• 通過遍歷數(shù)據(jù)結(jié)構(gòu)來定位目標(biāo)元素，例如數(shù)組、鏈表、樹和圖的遍歷等。
• 利用數(shù)據(jù)組織結(jié)構(gòu)或數(shù)據(jù)包含的先驗(yàn)信息，實(shí)現(xiàn)高效元素查找，例如二分查找、哈希查找和二叉搜索樹查找等。

不難發(fā)現(xiàn)，這些知識(shí)點(diǎn)都已在前面的章節(jié)中介紹過，因此搜索算法對于我們來說并不陌生。在本節(jié)中，我們將從更加系統(tǒng)的視角切入，重新審視搜索算法。

10.5.1   暴力搜索

暴力搜索通過遍歷數(shù)據(jù)結(jié)構(gòu)的每個(gè)元素來定位目標(biāo)元素。

• “線性搜索”適用于數(shù)組和鏈表等線性數(shù)據(jù)結(jié)構(gòu)。它從數(shù)據(jù)結(jié)構(gòu)的一端開始，逐個(gè)訪問元素，直到找到目標(biāo)元素或到達(dá)另一端仍沒有找到目標(biāo)元素為止。
• “廣度優(yōu)先搜索”和“深度優(yōu)先搜索”是圖和樹的兩種遍歷策略。廣度優(yōu)先搜索從初始節(jié)點(diǎn)開始逐層搜索，由近及遠(yuǎn)地訪問各個(gè)節(jié)點(diǎn)。深度優(yōu)先搜索是從初始節(jié)點(diǎn)開始，沿著一條路徑走到頭為止，再回溯并嘗試其他路徑，直到遍歷完整個(gè)數(shù)據(jù)結(jié)構(gòu)。

暴力搜索的優(yōu)點(diǎn)是簡單且通用性好，無須對數(shù)據(jù)做預(yù)處理和借助額外的數(shù)據(jù)結(jié)構(gòu)。

然而，此類算法的時(shí)間復(fù)雜度為 O(n) ，其中 n 為元素?cái)?shù)量，因此在數(shù)據(jù)量較大的情況下性能較差。

10.5.2   自適應(yīng)搜索

自適應(yīng)搜索利用數(shù)據(jù)的特有屬性（例如有序性）來優(yōu)化搜索過程，從而更高效地定位目標(biāo)元素。

• “二分查找”利用數(shù)據(jù)的有序性實(shí)現(xiàn)高效查找，僅適用于數(shù)組。
• “哈希查找”利用哈希表將搜索數(shù)據(jù)和目標(biāo)數(shù)據(jù)建立為鍵值對映射，從而實(shí)現(xiàn)查詢操作。
• “樹查找”在特定的樹結(jié)構(gòu)（例如二叉搜索樹）中，基于比較節(jié)點(diǎn)值來快速排除節(jié)點(diǎn)，從而定位目標(biāo)元素。

此類算法的優(yōu)點(diǎn)是效率高，時(shí)間復(fù)雜度可達(dá)到 O(log?n) 甚至 O(1) 。

然而，使用這些算法往往需要對數(shù)據(jù)進(jìn)行預(yù)處理。例如，二分查找需要預(yù)先對數(shù)組進(jìn)行排序，哈希查找和樹查找都需要借助額外的數(shù)據(jù)結(jié)構(gòu)，維護(hù)這些數(shù)據(jù)結(jié)構(gòu)也需要額外的時(shí)間和空間開支。

Note

自適應(yīng)搜索算法常被稱為查找算法，主要關(guān)注在特定數(shù)據(jù)結(jié)構(gòu)中快速檢索目標(biāo)元素。

10.5.3   搜索方法選取

給定大小為 n 的一組數(shù)據(jù)，我們可以使用線性搜索、二分查找、樹查找、哈希查找等多種方法在該數(shù)據(jù)中搜索目標(biāo)元素。各個(gè)方法的工作原理如圖 10-11 所示。

圖 10-11   多種搜索策略

上述幾種方法的操作效率與特性如表 10-1 所示。

表 10-1   查找算法效率對比

搜索算法的選擇還取決于數(shù)據(jù)體量、搜索性能要求、數(shù)據(jù)查詢與更新頻率等。

線性搜索

• 通用性較好，無須任何數(shù)據(jù)預(yù)處理操作。假如我們僅需查詢一次數(shù)據(jù)，那么其他三種方法的數(shù)據(jù)預(yù)處理的時(shí)間比線性搜索的時(shí)間還要更長。
• 適用于體量較小的數(shù)據(jù)，此情況下時(shí)間復(fù)雜度對效率影響較小。
• 適用于數(shù)據(jù)更新頻率較高的場景，因?yàn)樵摲椒ú恍枰獙?shù)據(jù)進(jìn)行任何額外維護(hù)。

二分查找

• 適用于大數(shù)據(jù)量的情況，效率表現(xiàn)穩(wěn)定，最差時(shí)間復(fù)雜度為 O(log?n) 。
• 數(shù)據(jù)量不能過大，因?yàn)榇鎯?chǔ)數(shù)組需要連續(xù)的內(nèi)存空間。
• 不適用于高頻增刪數(shù)據(jù)的場景，因?yàn)榫S護(hù)有序數(shù)組的開銷較大。

哈希查找

• 適合對查詢性能要求很高的場景，平均時(shí)間復(fù)雜度為 O(1) 。
• 不適合需要有序數(shù)據(jù)或范圍查找的場景，因?yàn)楣１頍o法維護(hù)數(shù)據(jù)的有序性。
• 對哈希函數(shù)和哈希沖突處理策略的依賴性較高，具有較大的性能劣化風(fēng)險(xiǎn)。
• 不適合數(shù)據(jù)量過大的情況，因?yàn)楣１硇枰~外空間來最大程度地減少?zèng)_突，從而提供良好的查詢性能。

樹查找

• 適用于海量數(shù)據(jù)，因?yàn)闃涔?jié)點(diǎn)在內(nèi)存中是離散存儲(chǔ)的。
• 適合需要維護(hù)有序數(shù)據(jù)或范圍查找的場景。
• 在持續(xù)增刪節(jié)點(diǎn)的過程中，二叉搜索樹可能產(chǎn)生傾斜，時(shí)間復(fù)雜度劣化至 O(n) 。
• 若使用 AVL 樹或紅黑樹，則各項(xiàng)操作可在 O(logn) 效率下穩(wěn)定運(yùn)行，但維護(hù)樹平衡的操作會(huì)增加額外開銷。