第21课：线性搜索（Linear Search）

学习目标

完成本课学习后，你将能够：

理解线性搜索的基本原理及其在计算机科学中的作用。
实现一个基本的线性搜索算法，并在无序列表中查找特定元素。
分析线性搜索的时间复杂度，理解其在不同数据规模下的性能。
明确线性搜索的适用场景与局限性，知道何时应选择其他算法。

核心概念

想象一下，你在一堆杂乱的文件中寻找一份特定的合同。最直接的方法是什么？没错，就是一份一份地翻看，直到找到目标文件或者翻完所有文件。这就是线性搜索（也称为顺序搜索）的核心思想。

线性搜索是一种最简单、最直观的搜索算法。 它的工作流程是：从数据集的第一个元素开始，逐个检查每一个元素，直到找到目标元素或者检查完所有元素为止。

它的关键特点是：

顺序扫描：必须按顺序访问每个元素，无法跳过。
无需排序：对数据的排列顺序没有要求，无论列表是否有序，它都能正常工作。
最坏情况：如果要找的元素恰好是最后一个，或者根本不在列表中，那么就必须检查完所有元素。

通俗解释：就像在人群中找你的朋友，你只能一个一个地看过去。如果朋友在人群中间或前面，你很快就找到了；如果他在最后面，或者根本不在，你就得把每个人都看一遍。

代码示例

让我们用Python来实现线性搜索，并附带一个简单的计数器来展示比较次数，直观感受其工作过程。

def linear_search(data_list, target):
    """
    在列表 data_list 中顺序搜索 target 元素。
    如果找到，返回其索引；如果未找到，返回 -1。
    """
    for index, value in enumerate(data_list):
        # 比较当前元素是否与目标值相等
        if value == target:
            return index  # 找到了，立即返回索引
    # 循环结束仍未找到，返回-1
    return -1

# 示例用法
if __name__ == "__main__":
    # 一个无序的数字列表
    numbers = [4, 2, 7, 1, 9, 3, 8, 5, 6]
    target_value = 3
    
    print(f"在列表 {numbers} 中搜索 {target_value}...")
    result_index = linear_search(numbers, target_value)
    
    if result_index != -1:
        print(f"找到！元素 {target_value} 在索引 {result_index} 处。")
    else:
        print(f"未在列表中找到 {target_value}。")
    
    # 演示搜索一个不存在的元素
    target_missing = 10
    print(f"\n尝试搜索 {target_missing}...")
    result_index = linear_search(numbers, target_missing)
    if result_index != -1:
        print(f"找到！元素 {target_missing} 在索引 {result_index} 处。")
    else:
        print(f"未在列表中找到 {target_missing}。")

代码输出：

在列表 [4, 2, 7, 1, 9, 3, 8, 5, 6] 中搜索 3...
找到！元素 3 在索引 5 处。

尝试搜索 10...
未在列表中找到 10。

时间复杂度分析：

最好情况：O(1) - 目标元素就是第一个。
最坏情况：O(n) - 目标元素是最后一个或不存在（n是列表长度）。
平均情况：O(n) - 平均需要检查一半的元素。它的时间复杂度与数据规模n成线性关系，这就是“线性搜索”名字的由来。

实践练习

练习1：基础搜索

给定列表 fruits = [‘apple’, ‘banana’, ‘cherry’, ‘date’, ‘elderberry’]，请使用线性搜索算法查找 'cherry’ 是否存在。如果存在，打印其索引；否则打印 "未找到"。 预期输出：

cherry 在索引 2 处。

练习2：搜索并处理重复项

编写一个函数 find_all_occurrences(data, target)，它使用线性搜索返回所有目标元素在列表中的索引（一个列表）。例如，对 data = [5, 2, 5, 8, 5] 和 target=5，应返回 [0, 2, 4]。 预期输出：

所有 5 的位置: [0, 2, 4]

练习3：模拟搜索过程

请编写一个带有详细步骤打印的线性搜索函数。每检查一个元素，都打印当前步骤和正在检查的值。如果找到目标，打印成功的步骤数；如果未找到，打印总检查步骤数。例如，搜索列表 [10, 20, 30, 40] 中的 30，输出应类似：

步骤 1: 检查索引 0, 值 10 -> 不匹配
步骤 2: 检查索引 1, 值 20 -> 不匹配
步骤 3: 检查索引 2, 值 30 -> 匹配！
成功在步骤 3 找到目标。

常见错误

循环条件写错：初学者有时会使用 range(len(data_list)-1)，导致漏掉检查最后一个元素。正确的循环范围是 range(len(data_list)) 或直接使用 enumerate。
```
# 错误示例：会漏掉最后一个元素
for i in range(len(data_list) - 1):
    if data_list[i] == target:
        ...
```

找到后未及时返回：在循环内部找到元素后，忘记使用 return 立即退出函数，导致继续无意义的循环，甚至可能覆盖掉正确的结果。

# 错误示例：可能返回错误的索引
result_index = -1
for i in range(len(data_list)):
    if data_list[i] == target:
        result_index = i # 记录下来，但没有退出！
    # 循环继续，如果后面有相同的元素，result_index会被更新
return result_index

修改了原始数据：线性搜索应该是只读操作。绝对不要在搜索函数内部去修改传入的列表，这会导致难以预料的副作用。

小结

线性搜索是最基础的搜索算法，其核心是逐个检查，顺序扫描。
它不需要数据有序，适用于任何可迭代的数据结构（列表、元组等）。
时间复杂度是 O(n)，随着数据量 n 的增加，搜索时间线性增长。对于大规模数据集，这可能很慢。
它是理解更高级搜索算法（如二分查找）的基石。二分查找正是为了优化线性搜索在有序数据上的低效率而出现的。
在数据量小或者数据无序的情况下，线性搜索因其简单性而是一个合理的选择。

关键要点：记住线性搜索的“耐心”和“直率”——它不会取巧，总是从头到尾忠实地检查每一份数据。虽然效率不高，但这份可靠性是它最重要的优点。下一课，我们将学习如何利用数据的有序性，用“二分查找”来大幅提升搜索效率。

练习编辑器

rust