线性查找

#线性查找

• 什么是线性查找
• 操作步骤
• 时间复杂度
• 适用场景

#什么是线性查找

线性查找（也叫顺序查找）是最简单直接的查找算法：从数组的第一个元素开始，逐个检查，直到找到目标或遍历完整个数组。

就像在一排人中找「张三」——你从第一个人开始问「你是张三吗？」，一个一个问下去，直到找到为止。

#操作步骤

在 3 9 8 2 1 4 6 5 7 中查找数字 6：

  3  9  8  2  1  4  6  5  7
  ↑
  3 ≠ 6，继续

  3  9  8  2  1  4  6  5  7
     ↑
     9 ≠ 6，继续

  3  9  8  2  1  4  6  5  7
        ↑
        8 ≠ 6，继续

  ...（继续检查 2、1、4）

  3  9  8  2  1  4 [6] 5  7
                    ↑
                   6 = 6，找到了！

Python 实现：

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i    # 找到了，返回索引
    return None         # 没找到

arr = [3, 9, 8, 2, 1, 4, 6, 5, 7]
print(linear_search(arr, 6))   # => 6
print(linear_search(arr, 10))  # => None

#时间复杂度

线性查找的时间复杂度为 O(n)——数据量越大，查找越慢。

#适用场景

线性查找的优点是不要求数据有序，实现简单。适合：

• 数据量小的场景
• 数据无序且不需要排序的场景
• 添加数据频繁、查找不频繁的场景（直接加在末尾即可，O(1)）

如果数据量大且需要频繁查找，应该先排序再用二分查找（O(log n)），或者使用哈希表（O(1)）。

#小结

• 线性查找从头到尾逐个检查，最简单直接的查找方式
• 不要求数据有序，但时间复杂度为 O(n)
• 适合小数据量或无序数据的场景