Hello 算法搜尋章節總結暴力搜尋、二分搜尋、雜湊查詢與樹查詢的選型實戰指南【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇技術指南以《Hello 算法》繁中版「搜尋」章節的總結summary.md為骨架系統梳理搜尋演算法的兩大類實現思路、各方法的時間複雜度對比與適用場景並結合章節內二分搜尋、插入點、邊界查詢與「以雜湊換時間」的兩數之和實戰以及倉庫中 Python 等 16 種語言的完整原始碼實作幫助讀者在面對真實資料規模與更新頻率時能快速做出正確的搜尋方法選型。搜尋演算法的兩大類實現思路搜尋演算法searching algorithm用於在資料結構例如陣列、鏈結串列、樹或圖中搜索一個或一組滿足特定條件的元素。根據實現思路可以將其劃分為以下兩類透過走訪資料結構來定位目標元素例如陣列、鏈結串列、樹和圖的走訪這類方法屬於「暴力搜尋」。利用資料組織結構或資料本身包含的先驗資訊實現高效元素查詢例如二分搜尋、雜湊查詢和二元搜尋樹查詢這類方法屬於「自適應搜尋」。章節原文searching_algorithm_revisited.md指出這些知識點其實都已在《Hello 算法》前面的章節中介紹過——陣列與鏈結串列走訪、樹的 BFS/DFS、雜湊表、二分搜尋等。因此本節的價值在於用更系統的視角把散落的知識重新整合成一份「選型決策框架」。暴力搜尋以走訪換通用性暴力搜尋透過走訪資料結構的每個元素來定位目標元素具體包含三種形態線性搜尋適用於陣列和鏈結串列等線性資料結構從一端開始逐個訪問元素直到找到目標元素或到達另一端。廣度優先搜尋BFS從初始節點開始逐層搜尋由近及遠地訪問各節點適用於圖和樹。深度優先搜尋DFS從初始節點開始沿一條路徑走到頭再回溯嘗試其他路徑直到走訪完整個資料結構。暴力搜尋的優點是簡單且通用性好無須對資料做預處理也不依賴額外的資料結構缺點是時間複雜度為 $O(n)$$n$ 為元素數量在資料量較大時效能較差。從倉庫原始碼可以直觀看到線性搜尋的實現形態。例如兩數之和的暴力解法two_sum.py就是典型的雙層迴圈走訪def two_sum_brute_force(nums: list[int], target: int) - list[int]: 方法一暴力枚举 # 两层循环时间复杂度为 O(n^2) for i in range(len(nums) - 1): for j in range(i 1, len(nums)): if nums[i] nums[j] target: return [i, j] return []自適應搜尋利用資料屬性實現高效查詢自適應搜尋利用資料的特有屬性例如有序性來最佳化搜尋過程二分搜尋利用資料的有序性實現高效查詢僅適用於陣列或基於陣列實現的資料結構。雜湊查詢利用雜湊表將搜尋資料與目標資料建立鍵值對對映從而實現查詢操作。樹查詢在特定樹結構如二元搜尋樹中基於比較節點值快速排除節點進而定位目標元素。此類演算法的優點是效率高時間複雜度可達 $O(\log n)$ 甚至 $O(1)$代價是通常需要對資料進行預處理——二分搜尋需要預先排序雜湊查詢和樹查詢需要藉助額外的資料結構而維護這些資料結構會帶來額外的時間與空間開銷。!!! tip自適應搜尋演算法常被稱為查詢演算法主要用於在特定資料結構中快速檢索目標元素。搜尋方法選取四種方法的效率對比表章節原文給出了一張完整的查詢演算法效率對比表這是全章最核心的選型依據完整羅列如下線性搜尋二分搜尋樹查詢雜湊查詢查詢元素$O(n)$$O(\log n)$$O(\log n)$$O(1)$插入元素$O(1)$$O(n)$$O(\log n)$$O(1)$刪除元素$O(n)$$O(n)$$O(\log n)$$O(1)$額外空間$O(1)$$O(1)$$O(n)$$O(n)$資料預處理/排序 $O(n \log n)$建樹 $O(n \log n)$建雜湊表 $O(n)$資料是否有序無序有序有序無序從表中可以看出沒有任何一種搜尋方法在所有維度上全面佔優。搜尋演算法的選擇還取決於資料規模、搜尋效能要求、資料查詢與更新頻率等因素需要綜合權衡。線性搜尋的適用場景通用性較好無須任何資料預處理。若只需查詢一次資料其他三種方法的預處理時間可能比線性搜尋本身更長。適用於體量較小的資料此時時間複雜度對效率的影響較小。適用於資料更新頻率較高的場景因為無須對資料進行額外維護。二分搜尋的適用場景適用於大資料量效率表現穩定最差時間複雜度為 $O(\log n)$。資料量不能過大因為儲存陣列需要連續的記憶體空間。不適用於高頻增刪資料的場景因為維護有序陣列的開銷較大。雜湊查詢的適用場景適合對查詢效能要求很高的場景平均時間複雜度為 $O(1)$。不適合需要有序資料或範圍查詢的場景因為雜湊表無法維護資料的有序性。對雜湊函式和雜湊衝突處理策略的依賴性較高具有較大的效能劣化風險。不適合資料量過大的情況因為雜湊表需要額外空間來最大程度減少衝突以保證良好的查詢效能。樹查詢的適用場景適用於海量資料因為樹節點在記憶體中是分散儲存的。適合需要維護有序資料或範圍查詢的場景。持續增刪節點可能使二元搜尋樹產生傾斜時間複雜度劣化至 $O(n)$。若使用 AVL 樹或紅黑樹各項操作可在 $O(\log n)$ 效率下穩定執行但維護樹平衡會增加額外開銷。二分搜尋深入區間寫法、複雜度與優缺點演算法流程與中點計算二分搜尋基於分治策略利用資料有序性每輪縮小一半搜尋範圍。其核心流程見 binary_search.py為初始化指標 $i 0$、$j n - 1$ 指向首尾元素雙閉區間 $[0, n-1]$迴圈中計算中點 $m \lfloor (i j) / 2 \rfloor$然後根據nums[m]與target的大小關係將區間收縮為 $[m1, j]$、$[i, m-1]$或在相等時直接返回 $m$若搜尋區間最終為空返回 $-1$。值得注意的是$i j$ 可能超出int型別的取值範圍。為了避免大數越界通常採用公式 $m \lfloor i (j - i) / 2 \rfloor$ 計算中點。Python 原始碼中因數字可無限大無須考慮此問題但在 C、Java、C 等定寬整數語言中這一寫法差異是實際編碼時必須注意的細節。雙閉區間與左閉右開區間除了雙閉區間 $[i, j]$常見的還有「左閉右開」區間 $[0, n)$其區間 $[i, j)$ 在 $i j$ 時為空。兩種寫法的初始化、迴圈條件i j對比i j與縮區間操作j m - 1對比j m均不同對比實現見 binary_search.py 中的binary_search_lcro函式。由於雙閉區間左右邊界對稱、更不容易出錯章節原文建議優先採用雙閉區間寫法。時間與空間複雜度時間複雜度為 $O(\log n)$區間每輪縮小一半迴圈次數為 $\log_2 n$。空間複雜度為 $O(1)$僅需指標 $i$、$j$ 的常數空間。優點與侷限性二分搜尋的優點是時間效率高如 $n 2^{20}$ 時線性查詢需 1048576 輪二分搜尋僅需 20 輪且無須額外空間。但其侷限性同樣明顯僅適用於有序資料若輸入無序為使用二分搜尋而專門排序往往得不償失排序 $O(n \log n)$ 高於線性查詢與二分搜尋頻繁插入元素時為維持有序性需 $O(n)$ 時間插入到特定位置代價昂貴。僅適用於陣列二分搜尋需要跳躍式訪問元素鏈結串列上跳躍訪問效率低。小資料量下線性查詢反而更佳線性查詢每輪僅 1 次判斷二分搜尋需 46 個單元操作$n$ 較小時線性查詢更快。變種一二分搜尋插入點二分搜尋不僅可用於查詢目標元素還可解決插入位置等變種問題。無重複元素時binary_search_insertion.py二分結束時 $i$ 指向首個大於target的元素、$j$ 指向最右一個小於target的元素因此插入索引即為 $i$若target存在插入點就是該元素索引。存在重複元素時binary_search_insertion.py普通二分只能返回某一個target無法確定最左位置。改進做法是當nums[m] target時執行j m - 1讓指標 $j$ 持續向小於target的元素收縮迴圈結束後 $i$ 便指向最左一個target。由於nums[m] target與nums[m] target兩分支操作相同兩者可合併但章節建議保留展開寫法以提升可讀性。變種二二分搜尋邊界查詢最左一個target左邊界本質上等價於查詢插入點呼叫插入點函式後檢查 $i$ 是否越界或nums[i] ! target滿足任一條件則返回 $-1$見 binary_search_edge.py。查詢右邊界有兩種取巧方法複用查詢左邊界將「查詢最右一個target」轉化為「查詢最左一個target 1」得到的插入點 $i$ 減 $1$ 即為 $j$見 binary_search_edge.py。轉化為查詢元素構造陣列中不存在的元素——查詢target - 0.5返回 $i$ 得左邊界查詢target 0.5返回 $j$ 得右邊界。此法需將target改為浮點數型別Python 無須改動。用雜湊查詢替換線性查詢兩數之和實戰在演算法題中將線性查詢替換為雜湊查詢是常用的時間最佳化策略。章節以「兩數之和」為例給定整數陣列nums與目標target在陣列中搜索「和」為target的兩個元素並返回索引。方法一暴力列舉以時間換空間。開啟兩層迴圈逐一判斷兩數之和時間複雜度 $O(n^2)$、空間複雜度 $O(1)$大資料量下非常耗時。方法二輔助雜湊表以空間換時間。維護鍵值對「陣列元素 → 元素索引」單層迴圈走訪每輪執行兩步判斷target - nums[i]是否已在雜湊表中若是則直接返回兩個索引將鍵值對nums[i]與索引i插入雜湊表。實現程式碼見 two_sum.pydef two_sum_hash_table(nums: list[int], target: int) - list[int]: 方法二辅助哈希表 # 辅助哈希表空间复杂度为 O(n) dic {} # 单层循环时间复杂度为 O(n) for i in range(len(nums)): if target - nums[i] in dic: return [dic[target - nums[i]], i] dic[nums[i]] i return []此方法將時間複雜度從 $O(n^2)$ 降至 $O(n)$代價是 $O(n)$ 的額外空間。儘管如此其整體時空效率更為均衡是本章題的最優解法也呼應了總結中「用雜湊查詢替換線性查詢可將時間複雜度從 $O(n)$ 降至 $O(1)$」的結論——在本例中則是從 $O(n^2)$ 降至 $O(n)$。總結如何選擇合適的搜尋方法回顧本章核心結論搜尋方法的選型應綜合考慮以下因素資料規模小資料選線性搜尋即可海量資料可考慮二分搜尋需連續記憶體或樹查詢節點分散儲存。搜尋效能要求對查詢效能要求極高且無須範圍查詢時優先考慮雜湊查詢$O(1)$。資料查詢與更新頻率高頻更新選線性搜尋零維護成本靜態有序大資料選二分搜尋需要動態維護有序與範圍查詢選樹查詢。是否允許額外資料結構二分搜尋無須額外空間雜湊查詢與樹查詢需要 $O(n)$ 額外空間與預處理成本。章節原文給出的一句總結可作為決策口訣線性搜尋適用於小型或頻繁更新的資料二分搜尋適用於大型、排序的資料雜湊查詢適用於對查詢效率要求較高且無須範圍查詢的資料樹查詢適用於需要維護順序和支援範圍查詢的大型動態資料。若想進一步鞏固可參考章節附帶的練習exercises.md手動推演二分搜尋每輪區間縮小過程、分析重複元素左右邊界的收縮方向以及為「$10^7$ 個有序靜態整數反覆查詢」「高頻增刪且無序的鍵存在性判斷」「無序陣列僅查詢一次」三種場景選擇合適方法。同時倉庫在 codes 目錄下提供了 Python、C、Java、C、C#、Go、Swift、Rust、Ruby、Kotlin、TypeScript、JavaScript、Dart、Zig 等多語言的對應實現如 binary_search.py、two_sum.py、binary_search_insertion.py、binary_search_edge.py每份程式碼均附可執行的 Driver Code 測試用例可直接運行驗證上述結論。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考