线性查找 (Linear Search)

算法原理

线性查找是最基础的查找算法之一。它从数组的第一个元素开始，逐一比较数组中的各个元素与目标值，直到找到相等的元素或搜索完整个数组。线性查找不要求数组是有序的，适用于任何类型的数组。

算法步骤

1. 从数组的第一个元素开始
2. 将当前元素与目标值进行比较
3. 如果相等，则返回当前元素的索引
4. 如果不相等，则移动到下一个元素
5. 重复步骤2-4，直到找到目标值或到达数组末尾
6. 如果到达数组末尾仍未找到目标值，则返回-1表示未找到

代码实现

public class LinearSearch {
    // 基本线性查找
    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 java.util.List findAllOccurrences(int[] arr, int target) {
        java.util.List indices = new java.util.ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                indices.add(i);
            }
        }
        return indices;
    }

    // 测试方法
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90, 25, 77};
        int target = 25;
        
        System.out.println("数组内容:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        
        int result = linearSearch(arr, target);
        if (result != -1) {
            System.out.println("找到了! 目标值 " + target + " 第一次出现在索引 " + result + " 处");
        } else {
            System.out.println("未找到目标值 " + target);
        }
        
        // 查找所有出现位置
        java.util.List allIndices = findAllOccurrences(arr, target);
        System.out.println("目标值 " + target + " 出现的所有位置: " + allIndices);
    }
}

应用场景

• 小型数据集合查找：当数据量较小时，线性查找简单直接
• 无序数据查找：对于未排序的数据，线性查找是唯一选择
• 一次性查找：只需要偶尔查找一两次的场景
• 查找所有匹配项：需要找出所有匹配元素的场景

优缺点