编辑“︁顺序搜索”︁

{{DISPLAYTITLE:顺序搜索}}

'''顺序搜索'''（Sequential Search），也称为'''线性搜索'''（Linear Search），是一种基础的搜索算法，用于在列表或数组中查找特定元素。其核心思想是'''逐个检查'''数据结构中的每个元素，直到找到目标值或遍历完所有元素。本文将详细介绍顺序搜索的原理、实现、复杂度分析及实际应用场景。

== 算法原理 ==
顺序搜索是最直观的搜索方法，适用于任何可遍历的数据结构（如数组、链表）。其步骤如下：
# 从数据结构的第一个元素开始。
# 依次将当前元素与目标值比较：
    # 若匹配，返回当前元素的索引或位置。
    # 若不匹配，继续检查下一个元素。
# 若遍历完所有元素仍未找到目标值，返回“未找到”的标识（如 `-1` 或 `None`）。

=== 数学描述 ===
对于长度为 <math>n</math> 的列表 <math>A = [a_1, a_2, \dots, a_n]</math> 和目标值 <math>x</math>，顺序搜索的数学表达为：
<math>
\text{返回最小的 } i \text{ 使得 } a_i = x \text{，否则返回 } -1.
</math>

== 代码实现 ==
以下是顺序搜索的常见编程语言实现示例：

=== Python 示例 ===
<syntaxhighlight lang="python">
def sequential_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index  # 找到目标，返回索引
    return -1  # 未找到目标

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

=== Java 示例 ===
<syntaxhighlight lang="java">
public class SequentialSearch {
    public static int sequentialSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;  // 找到目标，返回索引
            }
        }
        return -1;  // 未找到目标
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
        int target = 5;
        int result = sequentialSearch(arr, target);
        System.out.println("目标值 " + target + " 的索引是: " + result);  // 输出: 目标值 5 的索引是: 4
    }
}
</syntaxhighlight>

== 复杂度分析 ==
* '''时间复杂度'''：
    * 最坏情况：<math>O(n)</math>（目标值在末尾或不存在）。
    * 平均情况：<math>O(n)</math>。
    * 最好情况：<math>O(1)</math>（目标值在第一个位置）。
* '''空间复杂度'''：<math>O(1)</math>（仅需常数空间存储索引和临时变量）。

== 实际应用场景 ==
顺序搜索虽然简单，但在以下场景中仍有用武之地：
# '''小型数据集'''：当数据量较小时，顺序搜索的性能与高级算法（如二分搜索）差异不大。
# '''无序数据'''：若数据未排序，顺序搜索是唯一选择（除非先排序）。
# '''动态数据结构'''：如链表的搜索操作通常依赖顺序遍历。

=== 案例：学生名单查询 ===
假设有一个未排序的学生姓名列表，需要查找某位学生是否存在：
<syntaxhighlight lang="python">
students = ["Alice", "Bob", "Charlie", "David", "Eve"]
target_student = "David"
index = sequential_search(students, target_student)
if index != -1:
    print(f"{target_student} 存在于列表中，位置为 {index}.")
else:
    print(f"{target_student} 不存在于列表中.")
</syntaxhighlight>

== 优化与变体 ==
* '''哨兵值优化'''：在数组末尾添加目标值作为哨兵，减少循环内的比较次数（需确保数组可修改）。
* '''并行搜索'''：对于大型数据集，可将数据分块并行搜索（需多线程支持）。

== 与其他搜索算法对比 ==
{| class="wikitable"
|+ 搜索算法对比
! 算法 !! 适用条件 !! 时间复杂度 !! 空间复杂度
|-
| 顺序搜索 || 无序数据 || <math>O(n)</math> || <math>O(1)</math>
|-
| [[二分搜索]] || 有序数据 || <math>O(\log n)</math> || <math>O(1)</math>
|-
| [[哈希表搜索]] || 需预构建哈希表 || 平均 <math>O(1)</math> || <math>O(n)</math>
|}

== 可视化流程 ==
以下为顺序搜索在数组 <code>[10, 20, 30, 40]</code> 中查找目标值 <code>30</code> 的过程：
<mermaid>
graph TD
    A[开始] --> B[检查第一个元素: 10]
    B -- 不匹配 --> C[检查第二个元素: 20]
    C -- 不匹配 --> D[检查第三个元素: 30]
    D -- 匹配 --> E[返回索引 2]
</mermaid>

== 总结 ==
顺序搜索是搜索算法中最基础的一种，其实现简单但效率较低。尽管不适用于大规模数据，但在特定场景（如无序小数据集）中仍具实用性。理解顺序搜索有助于初学者掌握算法设计的核心思想，并为学习更高效的搜索方法奠定基础。

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:搜索算法]]