Searching

搜尋演算法學習筆記。

數組搜索算法

• 這些算法主要用於在排序或未排序的數組中進行搜索。
• 選擇哪種算法主要取決於數據是否排序、數據集大小、以及搜索頻率。

Binary Search

二分搜索 - 在已排序陣列中高效查找目標值

• Time Complexity
  • Best: $O(1)$
  • Average: $O(\log n)$
  • Worst: $O(\log n)$
• Space Complexity:
  • Iterative: $O(1)$
  • Recursive: $O(\log n)$

工作原理：在排序數組中查找目標值的位置。每次比較後將搜索範圍縮減一半。

使用場景：

• 大型已排序數據集
• 需要頻繁搜索的場景
• 調試時定位錯誤發生位置

Interpolation Search

插值搜索 - 針對均勻分布數據的優化搜索算法

• Time Complexity
  • Best: $O(1)$
  • Average (均勻分布數據): $O(\log(\log n))$
  • Worst (數據呈指數增長): $O(n)$
• Space Complexity: $O(1)$

探測公式：

工作原理：改進版二分搜索，根據目標值計算探測位置。適合均勻分布的數據。

使用場景：

• 大型排序且均勻分布的數值數組
• 數據分布較為均勻時效能優於二分搜索

圖搜索算法

• 這些算法用於在圖結構（如社交網絡、地圖等）中搜索路徑或特定節點。
• 選擇取決於問題的具體需求，如是否需要最短路徑、是否有明確的目標狀態等。

注: b為分支因子, m為最大深度, d為深度, V為頂點數, E為邊數

字符串搜索算法

• 主要用於文本處理、模式匹配等場景。
• 選擇取決於文本和模式的特性，以及是否需要處理多模式或模糊匹配。

注: n為文本長度, m為模式長度, k為字母表大小

概率搜索算法

• 這些算法通常用於複雜的優化問題或大規模搜索空間。
• 它們通常在傳統確定性算法效果不佳時使用。

注: b為分支因子, d為深度

特殊搜索算法

• 哈希搜索和布隆過濾器是兩種特殊的搜索方法，主要用於大規模數據集的快速查找和成員資格測試。

注: k為哈希函數數量, m為位數組大小, n為數據量