当前位置：首页 > news >正文

搜索算法之线性搜索详细解读（附带Java代码解读）

news 2025/7/8 9:51:19

1. 基本概念

线性搜索（Linear Search），也称为顺序搜索，是一种在列表中查找特定元素的算法。它从列表的第一个元素开始，逐个检查每个元素，直到找到目标元素或检查完所有元素。

2. 工作原理

线性搜索的操作过程如下：

初始化：从列表或数组的第一个元素开始。
遍历元素：按顺序访问每个元素。
比较：将当前元素与目标值进行比较。
匹配检查：
- 如果当前元素等于目标值，则返回当前索引（即位置）。
- 如果当前元素不等于目标值，则继续检查下一个元素。
结束条件：
- 如果找到目标值，返回其索引。
- 如果遍历完所有元素后未找到目标值，返回一个表示未找到的标志（通常是 -1）。

3. 算法步骤

以下是线性搜索的详细步骤：

输入：
- 一个列表或数组 arr。
- 一个目标值 target。
步骤：
- 初始化索引 i 为 0。
- 进入循环，直到 i 小于 arr.length。
  - 如果 arr[i] 等于 target，则返回 i。
  - 否则，增加 i，继续检查下一个元素。
- 如果循环结束后仍未找到目标值，返回 -1。

4. 时间复杂度分析

最坏情况：
- 当目标值不在数组中时，需要检查所有 n 个元素，时间复杂度为 O(n)。
最佳情况：
- 当目标值是第一个元素时，只需检查一次，时间复杂度为 O(1)。
平均情况：
- 通常需要检查一半的元素，时间复杂度为 O(n)，假设目标值均匀分布。

5. 空间复杂度

空间复杂度：线性搜索只需要少量的额外存储空间来存储索引变量，因此空间复杂度为 O(1)。

6. 实现代码

public class LinearSearch {/*** 执行线性搜索* @param arr 要搜索的数组* @param target 目标值* @return 目标值的索引，如果未找到返回-1*/public static int linearSearch(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[] numbers = {4, 2, 7, 1, 9, 3};// 目标值int target = 7;// 执行线性搜索int result = linearSearch(numbers, target);// 输出搜索结果if (result != -1) {System.out.println("元素 " + target + " 在数组中的索引是: " + result);} else {System.out.println("元素 " + target + " 不在数组中。");}}
}

代码解读：

public static int linearSearch(int[] arr, int target)：
- 定义了一个静态方法 linearSearch，接受两个参数：一个整数数组 arr 和一个目标值 target。
- 方法返回目标值的索引，如果未找到则返回 -1。
for (int i = 0; i < arr.length; i++)：
- 使用 for 循环遍历数组 arr 的每个元素。
- i 从 0 开始，到 arr.length - 1 结束。
if (arr[i] == target)：
- 在每次循环中，检查当前元素 arr[i] 是否等于目标值 target。
- 如果相等，返回当前索引 i。
return -1：
- 如果循环结束后仍未找到目标值，则返回 -1，表示目标值不在数组中。
public static void main(String[] args)：
- main 方法是程序的入口点，定义了一个示例数组 numbers 和一个目标值 target。
- 调用 linearSearch 方法，获取搜索结果并输出。