考纲要点

19.1.1 Linear search

项目	内容
描述	逐个检查列表中每个元素，直到找到目标或遍历完毕
前提条件	无 (可在未排序数据上运行)
步骤	1. 从第一个元素开始 2. 比较当前元素与目标值 3. 若匹配则返回位置 4. 否则移到下一个 5. 遍历完毕则返回未找到
时间复杂度	最好 $O(1)$，最坏 $O(n)$，平均 $O(n)$
空间复杂度	$O(1)$
优缺点	简单、无需排序；但大数据量时效率低

核心要点

• 适用于未排序和已排序列表
• 最简单的搜索算法
• 数据量小时推荐使用
• 不会修改原始数组

---

19.1.2 Binary search

项目	内容
描述	在已排序列表中通过反复将搜索范围减半来查找目标
前提条件	数据必须已排序
步骤 (Iterative)	1. 设置 first = 0, last = len(arr)-1 2. while first &lt;= last: 3. 计算 mid = (first + last) // 2 4. arr[mid] == target → 返回 5. arr[mid] < target → first = mid + 1 6. arr[mid] > target → last = mid - 1 7. 未找到则返回 -1
时间复杂度	最好 $O(1)$，最坏 $O(\log n)$
空间复杂度	Iterative: $O(1)$，Recursive: $O(\log n)$
优缺点	高效；但数据必须已排序

核心要点

• 每次迭代排除一半数据 → $O(\log n)$
• 必须保证数组已排序
• 注意 mid 使用整数除法 //
• 更新范围时必须跳过 mid: mid + 1 或 mid - 1
• 循环条件为 first <= last (包含等号)
• 递归实现必须 base case 在前
• 递归调用必须 return

---

对比总结

对比维度	Linear Search	Binary Search
数据要求	无需排序	必须排序
最好情况	$O(1)$ — 目标在第一个	$O(1)$ — 目标在中间
最坏情况	$O(n)$	$O(\log n)$
空间	$O(1)$	$O(1)$ 或 $O(\log n)$
实现难度	低	中
适用场景	小数据 / 未排序数据	大数据 / 已排序数据