目录

什么是线性查找？

时间复杂度分析

🧠 线性查找的优化

方法一：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 是“按表现升位”。