Что такое линейный поиск?

Question

Accepted Answer

**Линейный поиск** сканирует коллекцию элемент за элементом, пока не найдёт цель или не достигнет конца. Работает на **любом** списке — отсортированном или нет — но выполняется за время **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) пренебрежимо мал.
- Вам нужен одноразовый поиск, где построение индекса или сортировка предварительно не стоит усилий.

Если вы ищете многократно, предпочитайте отсортированный массив с binary search или hash set для среднего поиска O(1).

## Почему это важно

Линейный поиск — это эталон, относительно которого измеряются все остальные поиски.

Он напоминает вам, что *правильный* алгоритм зависит от данных: не отсортированные и маленькие благоприятствуют простому сканированию; большие и многократно запрашиваемые благоприятствуют более умным структурам.

Знание того, когда O(n) достаточно, предотвращает преждевременную оптимизацию.