顺序查找（Sequential Search）

顺序查找（又称线性查找，Linear Search）是一种最简单的查找算法。它的基本思想是 从数据序列的第一个元素开始，依次与目标值进行比较，直到找到匹配项或遍历完整个序列。

1. 顺序查找的基本原理

输入：数组 arr 和目标值 target。
过程：

从头到尾遍历数组。
逐个元素与 target 进行比较。
如果找到目标值，返回索引；否则返回 -1，表示未找到。

时间复杂度：

最优情况（Best Case）：O(1)（第一个元素就是目标值）。
最坏情况（Worst Case）：O(n)（目标值在最后，或不存在）。
平均情况（Average Case）：O(n)。

2. 顺序查找的代码实现

(1) 顺序查找（适用于无序数组）

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // 找到目标值，返回索引
        }
    }
    return -1; // 未找到目标值
}

int main() {
    int arr[] = {3, 8, 1, 4, 6, 9, 2};
    int target = 4;
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = linearSearch(arr, n, target);
    if (result != -1) {
        cout << "找到目标值 " << target << "，索引为：" << result << endl;
    } else {
        cout << "目标值 " << target << " 不存在" << endl;
    }

    return 0;
}

优缺点分析：

优点：适用于 无序数组，实现简单。
缺点：效率低，时间复杂度最坏为 O(n)。

(2) 顺序查找（适用于有序数组，带哨兵优化）

在有序数组中查找时，可以利用哨兵减少比较次数：

先在数组最后附加目标值（哨兵），避免越界判断。
找到目标值后，判断是否真的存在（避免哨兵误判）。

#include <iostream>
using namespace std;

int linearSearchWithSentinel(int arr[], int n, int target) {
    arr[n] = target; // 设定哨兵
    int i = 0;
    while (arr[i] != target) {
        i++;
    }
    return (i == n) ? -1 : i;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9}; 
    int target = 7;
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = linearSearchWithSentinel(arr, n, target);
    if (result != -1) {
        cout << "找到目标值 " << target << "，索引为：" << result << endl;
    } else {
        cout << "目标值 " << target << " 不存在" << endl;
    }

    return 0;
}

优化点：

哨兵（Sentinel）减少了 i < n 的检查，提高了执行效率。
适用于有序数组，但不如二分查找（O(log n)）高效。

3. 顺序查找 vs. 其他查找算法

查找算法	适用数据	时间复杂度	适用场景
顺序查找	无序数组	`O(n)`	适用于小规模数据
二分查找（Binary Search）	有序数组	`O(log n)`	适用于大规模有序数据
跳跃查找（Jump Search）	有序数组	`O(√n)`	适用于搜索较大的区间
散列表查找（Hash Search）	无序数据	`O(1)`	适用于键值映射
二叉搜索树（BST）查找	有序数据	`O(log n)`	适用于动态数据集合