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