零基础数据结构与算法——第四章：基础算法-搜索算法（上）
4.2 搜索算法
4.2.1 线性搜索（Linear Search）
基本概念
线性搜索（也称为顺序搜索）是最简单、最直观的搜索算法。它的核心思想是从数据集的一端开始，逐个检查每个元素，直到找到目标元素或者检查完所有元素。
线性搜索不要求数据集是有序的，可以应用于任何类型的数据集合。
生活中的例子
想象你在一堆纸质文件中寻找一份特定的文件：
- 你从第一份文件开始查看
- 逐个检查每份文件，看是否是你要找的那份
- 如果找到了，你就停止搜索
- 如果检查完所有文件都没找到，你就确定这份文件不在这堆文件中
这就是线性搜索的基本思想 - 一个一个地检查，直到找到或者确定不存在。
算法步骤
- 初始化：从数组的第一个元素开始
- 比较：将当前元素与目标值进行比较
- 匹配：如果当前元素等于目标值，返回当前位置，搜索结束
- 移动：如果当前元素不等于目标值，移动到下一个元素
- 重复：重复步骤2-4，直到找到目标值或者检查完所有元素
- 结束：如果检查完所有元素都没有找到目标值，返回-1或null表示未找到
图解过程
假设我们有数组：[5, 2, 8, 12, 3] 要查找元素 8
步骤1：检查索引0的元素 5 != 8，继续
[5, 2, 8, 12, 3]↑
当前位置
步骤2：检查索引1的元素 2 != 8，继续
[5, 2, 8, 12, 3]↑当前位置
步骤3：检查索引2的元素 8 == 8，找到目标值！返回索引2
[5, 2, 8, 12, 3]↑当前位置（找到目标）
代码实现
/*** 在数组中进行线性搜索* @param arr 要搜索的数组* @param target 要查找的目标值* @return 如果找到目标值，返回其索引；否则返回-1*/
public static int linearSearch(int[] arr, int target) {// 检查数组是否为空if (arr == null) {return -1;}// 从头到尾遍历数组for (int i = 0; i < arr.length; i++) {// 如果当前元素等于目标值，返回当前索引if (arr[i] == target) {return i;}}// 如果遍历完整个数组都没有找到目标值，返回-1return -1;
}// 泛型版本的线性搜索
public static <T> int linearSearch(T[] arr, T target) {if (arr == null || target == null) {return -1;}for (int i = 0; i < arr.length; i++) {// 使用equals方法比较对象if (target.equals(arr[i])) {return i;}}return -1;
}
性能分析
-
时间复杂度：
- 最坏情况：O(n) - 目标元素在数组的最后位置或不存在
- 最好情况：O(1) - 目标元素在数组的第一个位置
- 平均情况：O(n/2) ≈ O(n) - 平均需要检查一半的元素
-
空间复杂度：O(1) - 只需要常量级的额外空间
适用场景
- 数据集较小的情况
- 数据集是无序的
- 只需要进行一次性搜索
- 数据集经常变化，维护有序状态成本高
- 硬件层面的搜索（如CPU缓存、内存等）
线性搜索的优缺点
优点：
- 简单易实现
- 适用于任何数据类型
- 不需要数据集是有序的
- 对于小数据集效率可接受
缺点：
- 对于大数据集效率低
- 时间复杂度为O(n)，随着数据量增加，搜索时间线性增长
线性搜索的优化
- 提前终止：如果数据集有序，可以在发现当前元素大于目标值时提前终止
- 跳跃搜索：每次检查多个元素，如每次跳过2个或更多元素
- 二分搜索：如果数据集有序，可以使用二分搜索提高效率
- 哈希表：对于频繁搜索的场景，可以使用哈希表将时间复杂度降至O(1)