大家好，我是算法学长，一个热爱分享算法知识的开发者。算法 0 基础、校招冲刺中大厂，推荐使用算法导航：https://algo.codefather.cn/ 交互式算法学习平台，带大家系统化学习算法。

线性查找

介绍

线性查找（Linear Search），也称为顺序查找（Sequential Search），是最简单的一种查找算法。它的工作原理是：从数据结构的第一个元素开始，按顺序依次检查每个元素，直到找到目标值或者遍历完整个数据结构。线性查找不要求数据必须是有序的，适用于各种数据集合。

算法步骤

从数据结构的第一个元素开始
将当前元素与要查找的目标值进行比较
如果当前元素等于目标值，则查找成功，返回元素的位置
如果当前元素不等于目标值，则继续检查下一个元素
重复步骤2-4，直到找到目标值或者遍历完所有元素
如果遍历完所有元素仍未找到目标值，则查找失败，返回表示失败的信息（如-1）

核心特性

简单性：算法思路简单，易于实现
适用性：适用于任何数据结构，不需要需预先排序
时间复杂度：最好情况O(1)，最坏和平均情况均为O(n)
空间复杂度：O(1)，只需要常数级的额外空间

基础实现

下面是线性查找算法在各种主流编程语言中的实现：

Java实现

▼
java
复制代码
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;
            }
        }
        // 未找到目标值，返回-1
        return -1;
    }
    
    // 测试
    public static void main(String[] args) {
        int[] arr = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170};
        int target = 110;
        
        int result = linearSearch(arr, target);
        if (result == -1) {
            System.out.println("元素 " + target + " 不存在于数组中");
        } else {
            System.out.println("元素 " + target + " 在数组中的索引为 " + result);
        }
    }
}

JavaScript 实现

▼
javascript
复制代码
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

// 测试
const arr = [10, 20, 80, 30, 60, 50, 110, 100, 130, 170];
const target = 110;

const result = linearSearch(arr, target);
if (result === -1) {
    console.log(`元素 ${target} 不存在于数组中`);
} else {
    console.log(`元素 ${target} 在数组中的索引为 ${result}`);
}

Python 实现

▼
python
复制代码
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# 测试
arr = [10, 20, 80, 30, 60, 50, 110, 100, 130, 170]
target = 110

result = linear_search(arr, target)
if result == -1:
    print(f"元素 {target} 不存在于数组中")
else:
    print(f"元素 {target} 在数组中的索引为 {result}")

Go 实现

▼
go
复制代码
package main

import "fmt"

func linearSearch(arr []int, target int) int {
    for i := 0; i < len(arr); i++ {
        if arr[i] == target {
            return i
        }
    }
    return -1
}

func main() {
    arr := []int{10, 20, 80, 30, 60, 50, 110, 100, 130, 170}
    target := 110
    
    result := linearSearch(arr, target)
    if result == -1 {
        fmt.Printf("元素 %d 不存在于数组中\n", target)
    } else {
        fmt.Printf("元素 %d 在数组中的索引为 %d\n", target, result)
    }
}

C 实现

▼
c
复制代码
#include <stdio.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    int arr[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 110;
    
    int result = linearSearch(arr, n, target);
    if (result == -1) {
        printf("元素 %d 不存在于数组中\n", target);
    } else {
        printf("元素 %d 在数组中的索引为 %d\n", target, result);
    }
    
    return 0;
}

C++ 实现

▼
cpp
复制代码
#include <iostream>
#include <vector>

int linearSearch(const std::vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    std::vector<int> arr = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170};
    int target = 110;
    
    int result = linearSearch(arr, target);
    if (result == -1) {
        std::cout << "元素 " << target << " 不存在于数组中" << std::endl;
    } else {
        std::cout << "元素 " << target << " 在数组中的索引为 " << result << std::endl;
    }
    
    return 0;
}

优缺点

优点

实现极其简单，代码量少
不需要预先排序数据
适用于任何数据结构
对于小规模数据集效率可以接受
无额外空间要求

缺点

时间复杂度为O(n)，当数据量大时效率低下
不利用数据的任何特征（如有序性）来加速查找
对于有序数据，不如二分查找高效
随着数据规模增长，性能下降显著

应用场景

虽然线性查找效率不高，但在小部分场景中仍然有一定的适用性：

小规模数据集的查找
无序数据集的查找
仅需查找一次或偶尔查找的场景
对算法实现简单性要求高于效率的场景
作为其他高级查找算法的基础或回退方案
适合用作教学或算法入门学习

测验

线性查找的平均时间复杂度是多少？
当数据已经有序时，线性查找的效率会提高吗？为什么？
线性查找的空间复杂度是多少？为什么？

测验答案

线性查找的平均时间复杂度是O(n)。

不会。线性查找无论数据是否有序，都需要从头开始逐个检查，直到找到目标值或遍历完整个数据结构。

线性查找的空间复杂度是O(1)，它只需要常量级的额外空间来存储循环变量和比较结果，不随输入数据规模改变。

一文带你学会"线性查找"