线性查找
最后更新
线性查找（也叫顺序查找）是最简单的查找算法：从第一个元素开始，逐个与目标值比较，直到找到匹配项或检查完所有元素。它对数据不做任何假设，所以数组可以是无序的，元素也可以是任何能判断是否相等的东西。
上方的动画会在扫描从左向右推进时高亮每一次比较，一旦出现目标值就立即停止。简单的代价是速度：最坏情况下要检查每个元素，所以运行时间是 O(n)。如果数据已经有序，二分查找只需 O(log n) 就能得到同样的答案；如果需要先把数据排好序，可以看看归并排序。
时间复杂度与空间复杂度
| 情况 | 复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(1) | 第一个元素就是目标值。 |
| 平均情况 | O(n) | 平均要检查一半的元素才能命中。 |
| 最坏情况 | O(n) | 目标值在最后，或者根本不存在。 |
| 空间 | O(1) | 只需保存当前下标。 |
分步说明
| 步骤 | 发生了什么 |
|---|---|
| 1 | 从下标 0，也就是数组的第一个元素开始。 |
| 2 | 把当前元素与目标值比较。 |
| 3 | 如果相等，返回当前下标（找到了）。 |
| 4 | 否则向右移动一位，重复上述步骤。 |
| 5 | 如果到达数组末尾仍没有匹配，说明目标值不存在（返回 -1）。 |
实例演示
在 [7, 3, 9, 1, 5, 8, 2] 中查找 5：
| 比较次序 | 下标 | 元素 | 结果 |
|---|---|---|---|
| 1 | 0 | 7 | 7 ≠ 5：继续扫描。 |
| 2 | 1 | 3 | 3 ≠ 5：继续扫描。 |
| 3 | 2 | 9 | 9 ≠ 5：继续扫描。 |
| 4 | 3 | 1 | 1 ≠ 5：继续扫描。 |
| 5 | 4 | 5 | 5 = 5：在下标 4 处找到。 |
什么时候用线性查找
| 适合使用 | 不适合使用 |
|---|---|
| 数据无序，或者一直在变化 | 数据已经有序，这时二分查找快得多 |
| 集合很小，简单最重要 | 数据量很大，而且要反复查找 |
| 只能顺序访问数据（数据流、链表） | 你可以建立索引或哈希表，实现 O(1) 查找 |
Linear Search 代码
简洁、可运行的 Linear Search 实现，提供 Python, JavaScript, Java, C++, C, Pseudocode 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Linear Search 的 Python 代码
Python
1def linear_search(a, target):2 # Scan left to right until the target appears3 for i in range(len(a)):4 if a[i] == target:5 return i6 return -17
8
9nums = [7, 3, 9, 1, 5, 8, 2]10print("Index of 5:", linear_search(nums, 5))11print("Index of 4:", linear_search(nums, 4))Linear Search 的 JavaScript 代码
JavaScript
1function linearSearch(a, target) {2 // Scan left to right until the target appears3 for (let i = 0; i < a.length; i++) {4 if (a[i] === target) return i;5 }6 return -1;7}8
9const nums = [7, 3, 9, 1, 5, 8, 2];10console.log("Index of 5:", linearSearch(nums, 5));11console.log("Index of 4:", linearSearch(nums, 4));Linear Search 的 Java 代码
Java
1public class Main {2 static int linearSearch(int[] a, int target) {3 // Scan left to right until the target appears4 for (int i = 0; i < a.length; i++) {5 if (a[i] == target) return i;6 }7 return -1;8 }9
10 public static void main(String[] args) {11 int[] nums = {7, 3, 9, 1, 5, 8, 2};12 System.out.println("Index of 5: " + linearSearch(nums, 5));13 System.out.println("Index of 4: " + linearSearch(nums, 4));14 }15}Linear Search 的 C++ 代码
C++
1#include <iostream>2#include <vector>3
4int linearSearch(const std::vector<int>& a, int target) {5 // Scan left to right until the target appears6 for (std::size_t i = 0; i < a.size(); i++) {7 if (a[i] == target) return static_cast<int>(i);8 }9 return -1;10}11
12int main() {13 std::vector<int> nums = {7, 3, 9, 1, 5, 8, 2};14 std::cout << "Index of 5: " << linearSearch(nums, 5) << "\n";15 std::cout << "Index of 4: " << linearSearch(nums, 4) << "\n";16 return 0;17}Linear Search 的 C 代码
C
1#include <stdio.h>2
3int linear_search(const int a[], int n, int target) {4 /* Scan left to right until the target appears */5 for (int i = 0; i < n; i++) {6 if (a[i] == target) return i;7 }8 return -1;9}10
11int main(void) {12 int nums[] = {7, 3, 9, 1, 5, 8, 2};13 int n = sizeof(nums) / sizeof(nums[0]);14 printf("Index of 5: %d\n", linear_search(nums, n, 5));15 printf("Index of 4: %d\n", linear_search(nums, n, 4));16 return 0;17}Linear Search 的 Pseudocode 代码
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211
12FUNCTION linearSearch(target : INTEGER) RETURNS INTEGER13 DECLARE i : INTEGER14 // Scan left to right until the target appears15 FOR i ← 1 TO n16 IF nums[i] = target THEN17 RETURN i18 ENDIF19 NEXT i20 RETURN -121ENDFUNCTION22
23OUTPUT "Index of 5 is ", linearSearch(5)24OUTPUT "Index of 4 is ", linearSearch(4)线性查找常见问题
线性查找的时间复杂度是多少？
平均和最坏情况下是
O(n)（可能要访问每一个元素），最好情况下第一个元素就是目标值，为 O(1)。它只用 O(1) 的额外空间。线性查找需要数据有序吗？
不需要，这正是它的主要优点。线性查找逐个检查每个元素是否相等，与顺序无关，所以完全无序的数据也能用。相比之下，二分查找只能用于有序数组。
什么时候线性查找比二分查找更好？
当数据无序且只查找一次时（先排序要花
O(n log n)），当集合很小时，或者只能顺序访问数据时（比如数据流或链表）。如果要在有序数组上反复查找，二分查找更胜一筹。线性查找和顺序查找是一回事吗？
是的，这两个名字指的是同一个算法：按顺序扫描元素，直到找到目标值或到达集合末尾。
线性查找平均要比较多少次？
如果目标值存在，并且出现在任何位置的可能性相同，平均大约比较
n/2 次；如果目标值不存在，则正好比较 n 次。比较次数随数据量线性增长，这就是它叫线性查找的原因。相关资源
更多可视化
