資料結構：搜尋（Searching）
在電腦科學與資料結構領域，「搜尋」是一個至關重要的基本操作。無論是尋找特定資料、檢索資料庫記錄，還是進行文本匹配，搜尋都是資料處理中最常見的任務之一。
本篇文章將系統性探討搜尋的概念、不同資料結構上的搜尋方法、常見搜尋演算法的性能分析，並剖析其在實際應用中的影響。
一、搜尋的基本概念
1.1 搜尋的定義
搜尋（Searching）是指在給定資料集合中，找到滿足特定條件的元素，或判斷該元素是否存在的過程。
1.2 搜尋的輸入與輸出
- 輸入：一個資料集合 SSS 和一個目標值 kkk。
- 輸出：
- 若 k∈Sk \in Sk∈S，返回該元素的位置或該元素本身。
- 若 k∉Sk \notin Sk∈/S，返回「未找到」。
二、搜尋的分類
根據資料組織方式和搜尋目標的不同，搜尋可分為以下幾種：
| 類型 | 資料結構 | 說明 |
|---|---|---|
| 順序搜尋 | 陣列、鏈結串列 | 遍歷所有元素，逐一比對目標值。 |
| 二分搜尋 | 有序陣列 | 資料必須有序，每次排除一半區間，快速縮小範圍。 |
| 雜湊搜尋 | 雜湊表 | 根據關鍵字計算雜湊值，直接定位到對應位置。 |
| 樹搜尋 | 二元搜尋樹、平衡樹 | 根據樹的性質（如大小順序）逐層比對查找。 |
| 跳躍搜尋 | 有序鏈結串列 | 在鏈結串列上建立跳躍層次，加速搜尋。 |
三、常見搜尋演算法分析
3.1 順序搜尋（Linear Search）
描述：
- 適用於無序資料或小型資料集。
- 從頭到尾遍歷陣列，依次比較每個元素。
時間複雜度：
- 最佳情況：O(1)O(1)O(1)（目標在第一個位置）
- 最壞情況：O(n)O(n)O(n)（目標在最後或不存在）
- 平均情況：O(n)O(n)O(n)
優缺點：
- 優點：簡單、適用於任何資料結構。
- 缺點：資料量大時效率低。
3.2 二分搜尋（Binary Search）
描述：
- 適用於已排序資料。
- 每次將搜尋範圍減半。
演算法步驟：
- 設置左邊界lll和右邊界rrr。
- 計算中間位置m=⌊(l+r)/2⌋m = \lfloor (l + r) / 2 \rfloorm=⌊(l+r)/2⌋。
- 若A[m]=kA[m] = kA[m]=k，則找到。
- 若A[m]>kA[m] > kA[m]>k，縮小搜尋範圍至左半邊。
- 若A[m]<kA[m] < kA[m]<k，縮小搜尋範圍至右半邊。
時間複雜度：
- 最佳情況：O(1)O(1)O(1)
- 最壞情況：O(logn)O(\log n)O(logn)
- 平均情況：O(logn)O(\log n)O(logn)
優缺點：
- 優點：效率高，特別適用於靜態有序資料。
- 缺點：資料需事先排序；陣列插入、刪除成本較高。
3.3 雜湊搜尋（Hash Search）
描述：
- 適用於關鍵字查詢。
- 通過雜湊函數將關鍵字映射到陣列索引。
主要方法：
- 直接定址法：關鍵字即為陣列索引。
- 除法取餘法：h(k)=kmod mh(k) = k \mod mh(k)=kmodm。
- 乘法散列法：h(k)=⌊m(kAmod 1)⌋h(k) = \lfloor m(kA \mod 1) \rfloorh(k)=⌊m(kAmod1)⌋。
解決碰撞方法：
- 開放定址法：線性探測、二次探測、雙重雜湊。
- 鏈結法：將碰撞的元素存入同一個鏈結串列。
時間複雜度：
- 平均情況：O(1)O(1)O(1)
- 最壞情況：O(n)O(n)O(n)（全部碰撞）
優缺點：
- 優點：搜尋速度快，適合大量隨機資料。
- 缺點：需額外空間；碰撞處理增加複雜性。
3.4 樹搜尋（Binary Search Tree Search）
描述：
- 適用於動態資料集合。
- 根據大小順序排列，每個節點左小右大。
時間複雜度：
- 最佳情況：O(logn)O(\log n)O(logn)（平衡樹）
- 最壞情況：O(n)O(n)O(n)（退化為鏈表）
優缺點：
- 優點：支援插入、刪除操作；中序遍歷可得有序序列。
- 缺點：不平衡時性能下降。
進階版本：
- AVL 樹、紅黑樹、B 樹：保證平衡性，維持O(logn)O(\log n)O(logn)效率。
四、搜尋演算法性能比較總覽
| 搜尋方式 | 適用資料結構 | 平均時間複雜度 | 空間需求 | 適用情境 |
|---|---|---|---|---|
| 順序搜尋 | 陣列、鏈結串列 | O(n)O(n)O(n) | O(1)O(1)O(1) | 小型資料、無序集合 |
| 二分搜尋 | 有序陣列 | O(logn)O(\log n)O(logn) | O(1)O(1)O(1) | 大型靜態有序集合 |
| 雜湊搜尋 | 雜湊表 | O(1)O(1)O(1) | O(n)O(n)O(n) | 關鍵字檢索 |
| 樹搜尋 | 二元搜尋樹、平衡樹 | O(logn)O(\log n)O(logn) | O(n)O(n)O(n) | 動態資料集合，有序檢索 |
五、搜尋技術的實務應用
5.1 資料庫索引
- B 樹、B+ 樹用於資料庫索引。
- 雜湊索引提升關鍵字搜尋速度。
5.2 關鍵字查詢
- 雜湊表實現字典、標識符表。
- Trie 樹用於前綴搜尋、文本自動補全。
5.3 檔案系統
- B 樹處理大規模檔案索引。
- 雜湊法加速目錄檔案查找。
六、結論
搜尋演算法是資料處理領域的基石，其性能直接影響程式執行效率。在不同的應用場景下，應根據資料性質和操作頻率選擇最合適的搜尋方法。例如：
- 若資料靜態且經常查詢，選擇二分搜尋；
- 若資料隨機變動且需頻繁查找，選擇雜湊表；
- 若需保持資料有序，並支援範圍查詢，選擇平衡樹。
深入理解搜尋演算法的特性與適用場景，不僅能提升演算法設計能力，更是構建高效軟體系統的基礎。