目錄

什么是線性查找？

時間復雜度分析

🧠?線性查找的優化

方法一：Move to Front（哨兵）?

方法二：Transportation（向前交換一步）?

---

什么是線性查找？

我們先問：你想做什么？

你現在有一個數組：

A = [3, 5, 9, 7, 2, 6]

你想查找一個值，比如 7，問：

? 它在數組中的哪個位置？

從前往后，一個一個看！

也就是說：

• 比較 A[0] 是不是 7？不是

• 比較 A[1] 是不是 7？不是

• 比較 A[2] 是不是 7？不是

• 比較 A[3] 是不是 7？? 是！

找到它的位置啦，返回 3！

這就是——線性查找（Linear Search）?

從數組的 第一個元素開始，一個一個往后找，直到找到目標值，或者整個數組都遍歷完。?

• 數組 A，長度 n

• 要查找的目標值 key

查找過程：

• 遍歷數組中每一個元素

• 如果某個元素等于 key，返回它的索引

• 如果一直沒找到，說明它不存在，返回 -1

那么如果沒找到怎么辦？

你需要返回一個“不可能的合法索引”來表示失敗。

?為什么選 -1？

• 數組索引是從 0 開始的，最小索引是 0

• 所以 -1 永遠不是合法索引 → 非常適合表示 “查找失敗”

int linearSearch(int A[], int n, int key) {for (int i = 0; i < n; i++) {if (A[i] == key) {return i;  // 找到了，返回位置}}return -1;  // 沒找到
}

---

時間復雜度分析

情況	比較次數	時間復雜度
最好情況（第一個就找到）	1 次	O(1)
最壞情況（最后一個找到或找不到）	n 次	O(n)
平均情況	≈ n/2 次	O(n)

結論：🕒 時間復雜度是 O(n)

因為你可能需要檢查數組中每一個元素。?

空間復雜度分析

你只是訪問數組，沒有開新空間 → ? 空間復雜度是：O(1)（常數）

線性查找的適用場景

適合情況	不適合情況
?數組無序	?數組有序（用二分更快）
?數據量小	?數據量大
?查找頻率低	?查找頻率高

---

🧠?線性查找的優化

我們從最根本的問題問起：我們為什么需要優化線性查找？?

for (int i = 0; i < n; i++)if (A[i] == key)return i;

原始線性查找算法的時間復雜度是 O(n)，也就是說：

• 如果數組很長，查找一個元素可能非常慢；

• 每次都要從頭開始；

• 哪怕你經常查找的是第 98 個元素，也要前面白比對 97 次。

?Step 1：識別性能瓶頸

我們思考：

線性查找性能差的根源是什么？

答：不知道哪些值常用，每次都必須從頭查到尾。

?Step 2：尋找提升策略（性能原理）

我們繼續問：

有什么辦法能讓「經常被查找的值」查得更快？

思路：

• 如果某些值經常被查找，我們能不能讓它們靠前一點？

• 這樣，下次查找時更容易「提前命中」

這就是“利用訪問頻率的非均勻性（局部性）” —— 稀疏的優化策略

? Step 3：能不能改變數組順序？

思考：

原來的數組是按什么順序排的？

線性查找不要求有序 → ?我們可以調整順序！

也就是說，我們可以「根據使用情況」來調整數組布局，讓常查元素靠前

? Step 4：目標明確：讓“熱點元素”靠前

現在我們有了優化目標：

每次找到目標之后，想辦法把它往前移！

這樣下次更容易早找到。

?? Step 5：兩種“往前移”的方式自然浮現

方法一：Move to Front（哨兵）?

📌 思考方式：

既然你這么重要，我就把你提到最前面，以后第一個找你！

操作步驟：

1. 找到元素 A[i]

2. 將其值保存為 temp

3. 從 i 往前，把 A[j-1] 移動到 A[j]

4. 把 temp 放在 A[0]

為什么合理？

• 查過一次，就代表可能未來還會查 → 越早命中越好

• 不考慮“穩定性”，直接調整順序 → 速度最優

原地移動（圖示）

原數組：

[3][5][9][7][2]    ← 要查找 7↑

找到 A[3] == 7
→ 把 7 放到 A[0]
→ 其他人向后退一格：

結果：

[7][3][5][9][2]

優化后平均查找時間會降低，因為如果 7 是高頻元素，那么：

• 查找第一次：代價 O(n)

• 查找第二次：它已經在最前面了！→ O(1)

---

方法二：Transportation（向前交換一步）?

📌 思考方式：

如果你被查到了，我讓你「進一格」，但不會一下子到最前

操作步驟：

1. 找到元素 A[i]

2. 與 A[i?1] 交換

為什么要這么溫和？

• 如果一查就放最前，有可能誤判“偶然熱點”

• Transpose 是「緩慢上升」→ 更公平，更“穩定”

原地交換（圖示）

原數組：

[3][5][9][7][2]↑

找到 A[3] = 7
→ 與 A[2] = 9 交換

結果：

[3][5][7][9][2]

?下次再查到，就會再往前。

---

? Step 6：代碼實現

Move to Front：

int linearSearchMoveToFront(int A[], int n, int key) {for (int i = 0; i < n; i++) {if (A[i] == key) {// 將 A[i] 移動到前面int temp = A[i];for (int j = i; j > 0; j--) {A[j] = A[j - 1];}A[0] = temp;return 0;  // 返回新位置}}return -1;
}

Transportation：?

int linearSearchTranspose(int A[], int n, int key) {for (int i = 0; i < n; i++) {if (A[i] == key) {if (i > 0) {swap(A[i], A[i - 1]);return i - 1;}return i;}}return -1;
}

這就是從“行為本質”出發的兩種優化策略！

總結：

從第一性原理出發，線性查找的本質缺陷是“對所有元素一視同仁”。

而優化的核心思想是：

“把重要的人提前排隊”，不讓高頻元素總排在后面白等。

Move-to-front 是“VIP 通道”，Transpose 是“按表現升位”。?