查找演算法 (Searching Algorithms)#
查找是演算法中最基礎也最重要的操作。高效的查找演算法能將時間複雜度從線性 O(n) 降至對數 O(log n) 甚至常數 O(1)。
章節概覽#
| 演算法 | 時間複雜度 | 適用資料結構 | 核心要求 |
|---|---|---|---|
| 二分查找 | O(log n) | 陣列 | 有序、支援隨機存取 |
| 跳表 | O(log n) | 鏈結串列 | 多層索引 |
查找的本質#
查找的核心問題是：如何在一堆資料中快速定位目標？
| 查找方式 | 時間複雜度 | 做法 |
|---|---|---|
| 線性查找 | O(n) | 逐一比較 |
| 二分查找 | O(log n) | 每次排除一半 |
| 雜湊查找 | O(1) | 直接計算位置 |
選擇查找演算法時，要考慮：
- 資料是否有序
- 資料結構是否支援隨機存取
- 是否需要支援動態插入/刪除
跨倉庫導讀#
- 對應 LeetCode 練習：Binary Search ↗