---
title: "Линейный поиск"
url: https://algopath.pro/ru/patterns/linear-search
language: ru
summary: "Идите по коллекции с одного конца и остановитесь на первом подходящем элементе. Ни порядка, ни структуры, ни подготовки."
updated: 2026-08-24
---

# Линейный поиск

Идите по коллекции с одного конца и остановитесь на первом подходящем элементе. Ни порядка, ни структуры, ни подготовки.

## Линейный поиск: как это работает?

Начните с первого элемента коллекции. Спросите, тот ли это элемент.

Если он подошёл, остановитесь и верните его индекс. Смотреть дальше незачем.

Если не подошёл, перейдите к следующему. Задайте тот же вопрос снова.

Если конец наступил без совпадения, сообщите о неудаче. Обычно возвращают минус один или null.

Про данные не предполагается вообще ничего. Они могут быть отсортированы, перемешаны или ещё поступать.

Худший случай читает каждый элемент один раз. Лучший читает ровно один.

- `i = 0, значение 5` Ищем 2 в [5, 8, 2, 9]. Первый элемент мимо.
- `i = 1, значение 8` Совпадения по-прежнему нет. Идём к следующему индексу.
- `i = 2, значение 2` Этот элемент равен искомому.
- `возврат 2` Индекс уходит сразу. Девятку никто не читал.
- `цель 7 даёт -1` Отсутствующее значение стоит целого прохода. Это худший случай.

## Линейный поиск: когда применять?

- неотсортированный массив
- проверить каждый элемент
- нет гарантии порядка
- найти первое/любое совпадение
- малый n или разовый проход

## Линейный поиск: с чем путают?

- **Бинарный поиск (массив)** - Бинарному поиску нужны отсортированные данные, зато он платит log n. Перебор читает что угодно.
- **Хеш-множество / словарь** - Словарь отвечает мгновенно, но его надо сначала построить. Ради одного поиска перебор дешевле.
- **Два указателя (в одну сторону)** - Та пара переписывает массив прямо во время прохода. Поиск только читает.
- **Скользящее окно (переменное)** - Окно несёт описание живого отрезка. Перебор несёт максимум лучшее из увиденного.
- **Элементарные сортировки (выбором, пузырьком, вставками)** - Сортировка стоит O(n log n) и окупается при многих поисках. Один поиск её не окупает.

## Линейный поиск: сложность по времени и памяти

n примерно до 1e7 даёт O(n) времени и O(1) памяти. Больше или многократно, значит нужна структура.

## Линейный поиск: разбор примера

### Первый неповторяющийся символ

Дана строка. Верните индекс первого символа, который встречается ровно один раз.

Если все символы повторяются, верните минус один.

Посчитайте все символы за один проход. Хватит словаря с символом в ключе.

Потом пройдите строку слева ещё раз. Верните первый индекс со счётчиком один.

```javascript
function firstUniqChar(s) {
    const count = new Map();

    for (const c of s) {
        count.set(c, (count.get(c) ?? 0) + 1);
    }

    // the second pass is a plain scan: the first hit wins
    for (let i = 0; i < s.length; i++) {
        if (count.get(s[i]) === 1) return i;
    }

    return -1;
}
```

## Линейный поиск: частые ошибки

- **Перебирают внутри другого цикла** Перебор на каждый элемент превращает O(n) в O(n в квадрате). Постройте словарь один раз.
- **Возвращают значение вместо индекса** Такие задачи почти всегда просят позицию. Значение не скажет, где оно нашлось.
- **Забывают случай без совпадения** Цикл, дошедший до конца, всё равно обязан что-то вернуть. Выберите минус один и держитесь его.
- **Перебирают уже отсортированные данные** На отсортированном входе бинарный поиск куда дешевле. Проверьте вход до написания цикла.

## Линейный поиск: задачи с собеседований

- **Линейный поиск** Чистая форма: остановиться на первом совпадении.
- **Первый неповторяющийся символ** Посчитайте один раз, потом ищите счётчик один.
- **Поиск максимума** Держите лучшее найденное и сравнивайте с ним каждый элемент.
- **Есть ли дубликаты на крошечном входе** Вложенный перебор нормален, когда n очень мало.
- **Пропущенное число** Идите и сравнивайте каждый индекс с ожидаемым там значением.
- **Все индексы значения** Тот же проход, но без остановки на первом совпадении.
- **Мажоритарный элемент** Один проход со счётчиком даёт голосование Бойера-Мура.

## JavaScript

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

## Python

```python
def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1
```

## PHP

```php
function linearSearch(array $arr, $target) {
    foreach ($arr as $i => $x) {
        if ($x === $target) return $i;
    }
    return -1;
}
```