编辑“︁顺序搜索”︁

{{DISPLAYTITLE:顺序搜索}}

'''顺序搜索'''（Sequential Search），又称'''线性搜索'''（Linear Search），是最基础、最直观的搜索算法之一。它通过逐个检查数据结构中的元素，直到找到目标值或遍历完所有元素为止。顺序搜索适用于无序列表或简单数据结构，是初学者理解搜索算法的理想起点。

== 算法原理 ==
顺序搜索的核心思想是'''遍历'''。对于包含 ''n'' 个元素的列表，算法从第一个元素开始，依次与目标值比较：
* 若当前元素匹配目标值，返回其索引。
* 若遍历结束仍未找到匹配项，返回特定值（如 -1 或 `None`）。

数学表达为：给定列表 <math>A = [a_1, a_2, ..., a_n]</math> 和目标值 <math>x</math>，找到满足 <math>a_i = x</math> 的最小索引 <math>i</math>。

=== 时间复杂度分析 ===
* '''最坏情况'''：目标值位于列表末尾或不存在，需检查所有 ''n'' 个元素，时间复杂度为 <math>O(n)</math>。
* '''平均情况'''：假设目标值等概率出现在任意位置，平均比较次数为 <math>\frac{n+1}{2}</math>，时间复杂度仍为 <math>O(n)</math>。
* '''最好情况'''：目标值为第一个元素，时间复杂度为 <math>O(1)</math>。

== 代码实现 ==
以下是顺序搜索的通用实现（以 Python 为例）：

<syntaxhighlight lang="python">
def sequential_search(arr, target):
    """
    顺序搜索实现
    :param arr: 待搜索的列表
    :param target: 目标值
    :return: 目标值的索引（未找到返回 -1）
    """
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# 示例调用
data = [3, 1, 4, 1, 5, 9, 2, 6]
target_value = 5
result = sequential_search(data, target_value)
print(f"目标值 {target_value} 的索引为: {result}")  # 输出: 目标值 5 的索引为: 4
</syntaxhighlight>

=== 输入输出说明 ===
* 输入：无序列表 `[3, 1, 4, 1, 5, 9, 2, 6]`，目标值 `5`
* 输出：`4`（第一个匹配项的索引）

== 实际应用案例 ==
顺序搜索虽然效率不高，但在以下场景中仍有用武之地：
1. '''小型数据集'''：当数据量极小时（如少于 100 个元素），其实现简单性优于复杂算法。
2. '''无序数据'''：若数据未排序且仅需单次搜索，排序后再搜索可能更耗时。
3. '''实时数据流'''：如监控系统中逐条检查实时日志是否符合条件。

=== 案例：用户登录验证 ===
假设有一个未排序的用户名列表，检查输入用户名是否存在：
<syntaxhighlight lang="python">
usernames = ["alice", "bob", "charlie", "dave"]
input_name = "charlie"

if sequential_search(usernames, input_name) != -1:
    print("用户名存在！")
else:
    print("用户名不存在。")
</syntaxhighlight>

== 优化与变体 ==
虽然顺序搜索本身无法突破 <math>O(n)</math> 时间复杂度，但可通过以下方式优化实际性能：
* '''提前终止'''：若列表已排序，遇到大于目标值的元素时可立即终止搜索。
* '''哨兵值'''：在列表末尾添加目标值作为哨兵，减少循环内的比较次数（需确保列表可修改）。

=== 哨兵优化示例 ===
<syntaxhighlight lang="python">
def sequential_search_sentinel(arr, target):
    """
    使用哨兵优化的顺序搜索
    """
    arr.append(target)  # 添加哨兵
    index = 0
    while arr[index] != target:
        index += 1
    arr.pop()  # 移除哨兵
    return index if index < len(arr) else -1
</syntaxhighlight>

== 可视化流程 ==
以下为搜索目标值 `5` 的过程：
<mermaid>
graph LR
    A[开始] --> B[检查 3]
    B -- 不匹配 --> C[检查 1]
    C -- 不匹配 --> D[检查 4]
    D -- 不匹配 --> E[检查 1]
    E -- 不匹配 --> F[检查 5]
    F -- 匹配 --> G[返回索引 4]
</mermaid>

== 与其他搜索算法对比 ==
{| class="wikitable"
|+ 顺序搜索 vs 二分搜索
! 特性 !! 顺序搜索 !! 二分搜索
|-
| 数据要求 || 无需排序 || 必须有序
|-
| 时间复杂度 || <math>O(n)</math> || <math>O(\log n)</math>
|-
| 实现复杂度 || 简单 || 中等
|-
| 适用场景 || 小数据/无序数据 || 大数据/有序数据
|}

== 总结 ==
顺序搜索是搜索算法的基础，其核心思想是'''线性遍历'''。虽然效率不高，但在特定场景下仍具实用价值。理解顺序搜索有助于：
* 掌握算法设计的迭代思维
* 为学习更高效算法（如二分搜索、哈希表）奠定基础
* 处理简单或无需预处理的数据

{{算法导航}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:搜索算法]]