顺序查找（Sequential Search）

顺序查找是最简单的查找方法：从表的一端开始，逐个将记录的关键字与给定值比较，若某个记录的关键字与给定值相等，则查找成功；否则查找失败。 顺序查找适用于线性表，对数据是否有序没有要求。

查找过程

以数组 [3, 5, 1, 7, 2, 6]、目标 target = 7 为例，顺序查找的步骤如下：

1. 从下标 0 开始，逐个取出元素与 target 进行比较。
2. 若当前元素等于 target，则返回该元素的下标，查找成功。
3. 若遍历完整个表仍未找到，返回 -1，查找失败。

顺序查找过程模拟

步骤图：i=0，比较 nums[0]=3 ≠ 7

1/4

哨兵查找

在基础顺序查找中，每次循环需要检查两个条件：是否到达表尾和是否找到目标。哨兵查找通过在表头位置放置目标元素，消除每次对表尾的边界检查，从而减少约一半的比较次数。

哨兵法：在 nums[0] 处放置 target，从表尾向前扫描，必定在 nums[0] 处停止。若停在表尾之前说明找到了目标，否则查找失败。

方法	每次循环条件判断数	适用场景
基础顺序查找	2 次（边界 + 比较）	任意线性表
哨兵查找	1 次（仅比较）	可修改下标 0 的顺序表

算法特性

• 时间复杂度：O(n)。最坏情况下需比较 n 次（目标不存在或在末尾）；若各元素等概率被查找，平均比较次数为 (n+1)/2。
• 空间复杂度：O(1)，原地查找。只需常数额外空间存储指针与目标值。
• 无序也可用：不要求数组有序，适用范围最广。
• 稳定性：顺序查找返回第一个匹配项的位置。

Baseline 任务：顺序查找与哨兵查找

任务内容

完成 search.cpp，实现以下两个函数：

1. 顺序查找 int SequentialSearch(vector<int>& nums, int target)
   • 从表头开始逐个比较关键字，直到找到目标元素或扫描结束
   • 返回目标所在下标，未找到返回 -1
2. 哨兵查找 int SentinelSearch(vector<int>& nums, int target)
   • 在下标 0 处放置哨兵 target，从表尾向前扫描
   • 减少每次循环中的边界判断次数

文件结构

• search.h：函数声明
• search.cpp：查找算法核心实现
• test.cpp：测试程序，验证查找功能正确性

验证方式

• 编译：g++ -std=c++17 test.cpp search.cpp -o testSequentialSearch
• 运行：./testSequentialSearch