zh-hant/docs/chapter_searching/searching_algorithm_revisited.md
<u>搜尋演算法（searching algorithm）</u>用於在資料結構（例如陣列、鏈結串列、樹或圖）中搜索一個或一組滿足特定條件的元素。
搜尋演算法可根據實現思路分為以下兩類。
不難發現，這些知識點都已在前面的章節中介紹過，因此搜尋演算法對於我們來說並不陌生。在本節中，我們將從更加系統的視角切入，重新審視搜尋演算法。
暴力搜尋透過走訪資料結構的每個元素來定位目標元素。
暴力搜尋的優點是簡單且通用性好，無須對資料做預處理和藉助額外的資料結構。
然而，此類演算法的時間複雜度為 $O(n)$ ，其中 $n$ 為元素數量，因此在資料量較大的情況下效能較差。
自適應搜尋利用資料的特有屬性（例如有序性）來最佳化搜尋過程，從而更高效地定位目標元素。
此類演算法的優點是效率高，時間複雜度可達到 $O(\log n)$ 甚至 $O(1)$ 。
然而，使用這些演算法往往需要對資料進行預處理。例如，二分搜尋需要預先對陣列進行排序，雜湊查詢和樹查詢都需要藉助額外的資料結構，維護這些資料結構也需要額外的時間和空間開銷。
!!! tip
自適應搜尋演算法常被稱為查詢演算法，**主要用於在特定資料結構中快速檢索目標元素**。
給定大小為 $n$ 的一組資料，我們可以使用線性搜尋、二分搜尋、樹查詢、雜湊查詢等多種方法從中搜索目標元素。各個方法的工作原理如下圖所示。
上述幾種方法的操作效率與特性如下表所示。
<p align="center"> 表 <id> 查詢演算法效率對比 </p>| 線性搜尋 | 二分搜尋 | 樹查詢 | 雜湊查詢 | |
|---|---|---|---|---|
| 查詢元素 | $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)$ |
| 資料是否有序 | 無序 | 有序 | 有序 | 無序 |
搜尋演算法的選擇還取決規模、搜尋效能要求、資料查詢與更新頻率等。
線性搜尋
二分搜尋
雜湊查詢
樹查詢