Searching & Two Pointers · 比較表
搜尋與雙指標技巧比較
線性搜尋、二分搜尋、對答案二分、雙指標、滑動視窗：各自要求什麼前提、解決哪種問題。
| 演算法 | 時間 | 空間 | 前提 | 回答的問題 | 難度 |
|---|---|---|---|---|---|
| Linear Search線性搜尋 | O(n) | O(1) | 沒有 | x 在不在、在哪 | 入門 |
| Binary Search二分搜尋 | O(log n) | O(1) | 已排序、可隨機存取 | x 的位置、第一個 ≥ x 的位置 | 入門 |
| Binary Search on Answer二分答案 | O(n log R) | O(1) | 答案具單調性 | 最小可行值／最大可行值 | 困難 |
| Two Pointers雙指標 | O(n) | O(1) | 已排序，或兩端可收斂 | 配對、去重、分割 | 進階 |
| Sliding Window滑動視窗 | O(n) | O(k) | 連續區間、可增量維護 | 最長／最短／計數的子陣列 | 進階 |
什麼時候選哪一個
Linear Search 線性搜尋
資料無序、只查一次、或 n 很小。查很多次就先排序或改用雜湊表。
Binary Search 二分搜尋
排好序的陣列上找值或找邊界（lower_bound）。鏈結串列不行，沒有 O(1) 的中點。
Binary Search on Answer 二分答案
題目問「最小的 x 使得…成立」，而且 x 越大越容易成立（或越難）。把判定寫成 check(x)，對 x 二分。
Two Pointers 雙指標
有序陣列找和為 k 的兩數、原地去重、把陣列分成兩類。指標各自單向移動，總共 O(n)。
Sliding Window 滑動視窗
「連續子陣列／子字串」滿足某條件的最長或最短。右端擴張、左端收縮，區間狀態能 O(1) 增減。
選擇指南
- 有序 + 找一個值或邊界 → 二分搜尋。有序 + 找一對 → 雙指標。
- 「連續」兩個字出現 → 滑動視窗。子序列（不連續）不是視窗，通常是 DP。
- 問最小／最大的可行值，而不是位置 → 對答案二分。關鍵字：「最少需要多少」「最大能到多少」「最小化最大值」。
- 視窗內的條件無法 O(1) 更新（例如視窗中位數）→ 滑動視窗不夠，要配單調佇列、平衡樹或兩個堆積。
- 無序又要常查 → 不是搜尋演算法的問題，先排序（O(n log n) 一次）或改用雜湊表（O(1) 每次）。