顺序查找Linear search

依次检查候选，直到找到目标或遍历结束。

核心约束: 未检查部分仍可能包含目标。
适用问题: 小集合、无序输入、顺序数据流。
边界与取舍: 数据变大后，重复查询通常需要建立索引。

时间与空间#

n 为候选数；单次相等比较 $O(1)$ 。

时间复杂度: 最坏 $O(n)$ ；最好 $O(1)$
辅助空间: $O(1)$

顺序检查直到找到目标或耗尽输入，不要求有序。成功查找的平均成本要指定目标位置分布，不能无条件给固定比例。

基础原理参考资料

NIST · Linear search逐个检查的算法定义及别名。

Princeton · SequentialSearchST使用线性扫描的符号表及最坏时间界。