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

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

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

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

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

10.5.1   暴力搜索

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

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

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

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

10.5.2   自適應(yīng)搜索

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

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

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

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

Note

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

10.5.3   搜索方法選取

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

圖 10-11   多種搜索策略

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

表 10-1   查找算法效率對(duì)比

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

線(xiàn)性搜索

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

二分查找

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

哈希查找

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

樹(shù)查找

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