什么是线性搜索？

Question

什么是线性搜索？

Accepted Answer

**Linear search** 逐个扫描集合中的元素，直到找到目标或到达末尾。它适用于**任何**列表——无论是否排序——但运行时间为 **O(n)**。

## 思想

无需假设顺序：只需逐个检查每一项。

## 示例

```python
def linear_search(arr, target):
    for i, value in enumerate(arr):   # walk left to right
        if value == target:
            return i                  # return the index when found
    return -1                         # not found after full scan

linear_search([4, 2, 7, 1], 7)        # -> 2
```

## 复杂度

- **时间：** O(n) 最坏情况（目标在末尾或不存在），O(1) 最好情况。
- **空间：** O(1)。

## 何时使用

- 数据**未排序**且无法承受排序的成本。
- 列表很小，O(n) 可以忽略不计。
- 需要一次性查询，其中构建索引或事先排序不值得。

如果重复搜索，请优先使用排序数组加二叉搜索或使用哈希集进行 O(1) 平均查询。

## 为什么这很重要

Linear search 是其他所有搜索算法的测量基准。

它提醒你*正确的*算法取决于数据：无序且很小的数据适合简单扫描；大且需要反复查询的数据适合更智能的数据结构。

了解何时 O(n) 足够好可以防止过度优化。