课程信息
B2.4 · 搜索 · 已学习

线性搜索

依次检查元素，找到第一个匹配值。重温课程，练习终止条件。

55 分钟

本节课资源

打开学生讲义（PDF）（英文文件） 课堂活动 ↓ 在 Python 中尝试示例 →
动画： 线性搜索二分搜索
Python · 逐步执行

线性搜索

依次检查各值，在首次匹配时停止。

选择“播放”或“下一行”，跟踪 Python 的执行过程。

Python 实现

高亮表示下一条将执行的语句。数值显示执行该行之前的状态。

def linear_search(items, target):    for index in range(len(items)):        if items[index] == target:            return index    return -1

目标位于第一个位置时是最佳情况，时间复杂度为 O(1)。目标位于末尾或不存在时为 O(n)。此实现使用 O(1) 辅助空间。

学完本节课后

  • 返回第一个匹配索引，目标不存在时返回 -1。
  • 跟踪算法并统计比较次数。
  • 测试空列表、重复值与边界位置。

按自己的节奏通过这些活动复习主题。时长仅供参考。

复习课程

01 · 5 分钟

回顾

解释栈与队列的区别，再预测按索引遍历 Python 列表的结果。

02 · 10 分钟

设计

使用 numbers = [7, 3, 9, 2, 6] 和 target = 9。描述如何在不使用 in 或 index() 的情况下找到目标值。

03 · 10 分钟

跟踪

记录索引、当前值、比较与结果。比较首次匹配即停止与继续检查到末尾两种方式。

04 · 20 分钟

实现

编写 find_first(items, target)。返回第一个匹配索引；只有检查完所有候选项后才能返回 -1。对 []、[4] 和 [4, 7, 4] 分别测试存在与不存在的目标。

05 · 10 分钟

解释

解释最佳与最坏情况。统计目标在首位、末位或不存在时的比较次数。描述数据有序时会有什么变化。

下课前

离堂问题

为什么 return -1 必须放在循环之后，而不能放在首次比较失败之后？