C / C++ / 系统课时

顺序查找适合什么数据

顺序查找适合什么数据

顺序查找从数据的一端开始逐个比较,直到找到目标值或扫描结束。它不要求数据提前排序,也不依赖额外索引,因此特别适合规模较小、结构简单或只偶尔查询的数据。本节实现线性查找,并用比较次数理解 O(n)O(n) 的含义。

学习目标

  • 能实现返回目标下标的顺序查找
  • 理解顺序查找为什么不要求数据有序
  • 能根据数据规模和查询频率判断它是否合适

顺序查找的规则

给定数组和目标值,从下标 0 开始依次比较。遇到第一个相等元素就返回它的下标;如果遍历完整个数组仍未找到,则返回一个约定好的失败值,例如 -1。

这个过程只依赖“能否逐个读取元素”和“能否比较是否相等”,所以数组即使完全无序也可以查找。代价是没有办法像二分查找那样一次排除一半数据。

实现线性查找

下面的函数接收整数数组、元素个数和目标值。size_t 用于表示数组长度和下标,返回值使用 int,以便用 -1 表示未找到。

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

预期输出

text
index = 2

这里的数据顺序是 42, 7, 19, 3, 25,并未排序,但查找仍能正确工作。如果目标值不存在,函数会扫描到末尾并返回 -1。

O(n) 到底表示什么

顺序查找的最好情况是目标正好位于第一个元素,只比较 1 次;最坏情况是目标位于最后一个元素,或者根本不存在,需要比较 n 次。因此最坏时间复杂度是 O(n)O(n)。

O(n) 并不表示每次一定比较 n 次,而是表示当数据规模增大时,最坏情况下的比较次数与元素数量成线性关系。数组从 100 个元素增长到 1000 个元素,最坏比较次数也大约增长到原来的 10 倍。

空间方面,算法只使用循环下标和少量局部变量,没有创建与数据规模相关的额外结构,因此额外空间复杂度是 O(1)O(1)。

哪些数据适合顺序查找

顺序查找通常适合以下场景:

  • 数据量较小,扫描全部元素的成本可接受
  • 数据没有排序,而且不值得为了少量查询先排序
  • 数据经常变化,维护额外索引的成本高于直接扫描
  • 只执行一次或很少几次查找,建立哈希表或其他索引不划算

如果同一批数据需要大量重复查询,顺序查找会反复执行相似扫描。这时可以考虑排序后使用二分查找,或者建立哈希表,把预处理成本换成更快的后续查询。

两个容易忽略的边界

空数组也是合法输入。只要 length 为 0,循环不会执行,函数直接返回 -1;因此不需要访问任何数组元素。

如果数组中有重复值,当前实现返回第一个匹配位置。若业务需要找到全部匹配项,就不能在第一次相等时立即返回,而应继续扫描并收集结果。顺序查找是否合适,最终取决于数据规模、查询次数和是否值得维护额外结构,而不是数据是否有序。

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

目录与阅读设置

阅读设置

17

记录一个想法

顺序查找适合什么数据

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

登录哪都通