C / C++ / 系统课时
在数组中查找指定元素
在数组中查找指定元素
当数组中保存了多条同类型数据时,最直接的查找方式是从第一个元素开始逐个比较,直到找到目标值或扫描结束。本节用一个完整的线性查找程序说明索引返回、未找到处理和常见边界。
学习目标
- 能用循环实现数组的线性查找,并返回目标元素索引
- 能用明确的返回值区分“找到”和“未找到”
- 能判断重复值、空数组和查找成本等边界
线性查找解决什么问题
如果数组没有提前排序,也没有额外索引结构,就不能直接判断目标值位于哪里。线性查找会按索引 0、1、2……依次读取元素,并把当前元素与目标值比较。
只要某次比较相等,就可以立即返回当前索引;如果循环结束仍没有相等元素,就返回一个不可能成为合法索引的值。对 C 数组而言,使用 -1 表示“未找到”简单且直观。
例如数组 {12, 7, 19, 3, 25} 中查找 19,比较顺序是 12、7、19。命中后不需要继续检查后面的元素,因此实际比较次数取决于目标所在位置。
编写完整查找程序
下面把查找逻辑封装为 linear_search。函数接收数组、元素个数和目标值;找到时返回索引,找不到时返回 -1。
#include <stdio.h>
int linear_search(const int values[], int length, int target) {
for (int i = 0; i < length; ++i) {
if (values[i] == target) {
return i; // 首次命中后立即结束查找
}
}
return -1; // 合法数组索引不会是负数
}
int main(void) {
int numbers[] = {12, 7, 19, 3, 25};
int length = (int)(sizeof(numbers) / sizeof(numbers[0]));
int target = 19;
int index = linear_search(numbers, length, target);
if (index >= 0) {
printf("target=%d found at index %d\n", target, index);
} else {
printf("target=%d not found\n", target);
}
return 0;
}预期输出
target=19 found at index 2这里返回的是数组索引而不是“第几个元素”。索引从 0 开始,所以索引 2 对应数组中的第三个元素。
正确处理未找到与重复值
-1 只负责表达“没有合法索引”。调用者拿到结果后必须先判断 index >= 0,再把它用于访问数组,否则可能产生越界访问。
如果数组中存在重复值,例如 {4, 8, 4, 9},当前实现会返回第一个 4 的索引 0。如果业务需要找出全部匹配项,就不能在第一次命中后 return,而应继续遍历并记录所有索引。
长度为 0 时,循环一次都不会执行,函数会直接返回 -1。因此只要调用者传入的 length 与真实元素数量一致,这个实现不需要为“空数组”增加特殊分支。
判断什么时候适合线性查找
线性查找最坏需要检查全部 n 个元素,时间复杂度是 ,额外空间复杂度是 。它适合数据量较小、数组未排序,或只进行少量查找的场景。
如果同一批数据需要被频繁查询,继续反复线性扫描通常不划算。此时可以根据数据特点考虑先排序后使用二分查找,或使用更适合检索的数据结构。对基础数组而言,线性查找仍是最容易验证、也最不依赖前置条件的方案。