目錄
什么是線性查找?
時間復雜度分析
🧠?線性查找的優化
方法一: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(哨兵)?
📌 思考方式:
既然你這么重要,我就把你提到最前面,以后第一個找你!
操作步驟:
-
找到元素 A[i]
-
將其值保存為 temp
-
從 i 往前,把 A[j-1] 移動到 A[j]
-
把 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(向前交換一步)?
📌 思考方式:
如果你被查到了,我讓你「進一格」,但不會一下子到最前
操作步驟:
-
找到元素 A[i]
-
與 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 是“按表現升位”。?