C / C++ / 系统课时
顺序查找适合什么数据
顺序查找适合什么数据
顺序查找从数据的一端开始逐个比较,直到找到目标值或扫描结束。它不要求数据提前排序,也不依赖额外索引,因此特别适合规模较小、结构简单或只偶尔查询的数据。本节实现线性查找,并用比较次数理解 的含义。
学习目标
- 能实现返回目标下标的顺序查找
- 理解顺序查找为什么不要求数据有序
- 能根据数据规模和查询频率判断它是否合适
顺序查找的规则
给定数组和目标值,从下标 0 开始依次比较。遇到第一个相等元素就返回它的下标;如果遍历完整个数组仍未找到,则返回一个约定好的失败值,例如 -1。
这个过程只依赖“能否逐个读取元素”和“能否比较是否相等”,所以数组即使完全无序也可以查找。代价是没有办法像二分查找那样一次排除一半数据。
实现线性查找
下面的函数接收整数数组、元素个数和目标值。size_t 用于表示数组长度和下标,返回值使用 int,以便用 -1 表示未找到。
#include <stdio.h>
#include <stddef.h>
int linear_search(const int data[], size_t length, int target) {
for (size_t i = 0; i < length; ++i) {
// 找到第一个匹配位置后立即结束,不再继续扫描。
if (data[i] == target) {
return (int)i;
}
}
return -1;
}
int main(void) {
int data[] = {42, 7, 19, 3, 25};
size_t length = sizeof(data) / sizeof(data[0]);
int index = linear_search(data, length, 19);
printf("index = %d\n", index);
return 0;
}预期输出
index = 2这里的数据顺序是 42, 7, 19, 3, 25,并未排序,但查找仍能正确工作。如果目标值不存在,函数会扫描到末尾并返回 -1。
O(n) 到底表示什么
顺序查找的最好情况是目标正好位于第一个元素,只比较 1 次;最坏情况是目标位于最后一个元素,或者根本不存在,需要比较 n 次。因此最坏时间复杂度是 。
O(n) 并不表示每次一定比较 n 次,而是表示当数据规模增大时,最坏情况下的比较次数与元素数量成线性关系。数组从 100 个元素增长到 1000 个元素,最坏比较次数也大约增长到原来的 10 倍。
空间方面,算法只使用循环下标和少量局部变量,没有创建与数据规模相关的额外结构,因此额外空间复杂度是 。
哪些数据适合顺序查找
顺序查找通常适合以下场景:
- 数据量较小,扫描全部元素的成本可接受
- 数据没有排序,而且不值得为了少量查询先排序
- 数据经常变化,维护额外索引的成本高于直接扫描
- 只执行一次或很少几次查找,建立哈希表或其他索引不划算
如果同一批数据需要大量重复查询,顺序查找会反复执行相似扫描。这时可以考虑排序后使用二分查找,或者建立哈希表,把预处理成本换成更快的后续查询。
两个容易忽略的边界
空数组也是合法输入。只要 length 为 0,循环不会执行,函数直接返回 -1;因此不需要访问任何数组元素。
如果数组中有重复值,当前实现返回第一个匹配位置。若业务需要找到全部匹配项,就不能在第一次相等时立即返回,而应继续扫描并收集结果。顺序查找是否合适,最终取决于数据规模、查询次数和是否值得维护额外结构,而不是数据是否有序。