C / C++ / 系统课时

在数组中查找指定元素

在数组中查找指定元素

当数组中保存了多条同类型数据时,最直接的查找方式是从第一个元素开始逐个比较,直到找到目标值或扫描结束。本节用一个完整的线性查找程序说明索引返回、未找到处理和常见边界。

学习目标

  • 能用循环实现数组的线性查找,并返回目标元素索引
  • 能用明确的返回值区分“找到”和“未找到”
  • 能判断重复值、空数组和查找成本等边界

线性查找解决什么问题

如果数组没有提前排序,也没有额外索引结构,就不能直接判断目标值位于哪里。线性查找会按索引 0、1、2……依次读取元素,并把当前元素与目标值比较。

只要某次比较相等,就可以立即返回当前索引;如果循环结束仍没有相等元素,就返回一个不可能成为合法索引的值。对 C 数组而言,使用 -1 表示“未找到”简单且直观。

例如数组 {12, 7, 19, 3, 25} 中查找 19,比较顺序是 12、7、19。命中后不需要继续检查后面的元素,因此实际比较次数取决于目标所在位置。

编写完整查找程序

下面把查找逻辑封装为 linear_search。函数接收数组、元素个数和目标值;找到时返回索引,找不到时返回 -1。

c
#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;
}

预期输出

text
target=19 found at index 2

这里返回的是数组索引而不是“第几个元素”。索引从 0 开始,所以索引 2 对应数组中的第三个元素。

正确处理未找到与重复值

-1 只负责表达“没有合法索引”。调用者拿到结果后必须先判断 index >= 0,再把它用于访问数组,否则可能产生越界访问。

如果数组中存在重复值,例如 {4, 8, 4, 9},当前实现会返回第一个 4 的索引 0。如果业务需要找出全部匹配项,就不能在第一次命中后 return,而应继续遍历并记录所有索引。

长度为 0 时,循环一次都不会执行,函数会直接返回 -1。因此只要调用者传入的 length 与真实元素数量一致,这个实现不需要为“空数组”增加特殊分支。

判断什么时候适合线性查找

线性查找最坏需要检查全部 n 个元素,时间复杂度是 O(n)O(n),额外空间复杂度是 O(1)O(1)。它适合数据量较小、数组未排序,或只进行少量查找的场景。

如果同一批数据需要被频繁查询,继续反复线性扫描通常不划算。此时可以根据数据特点考虑先排序后使用二分查找,或使用更适合检索的数据结构。对基础数组而言,线性查找仍是最容易验证、也最不依赖前置条件的方案。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

在数组中查找指定元素

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通