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

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

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

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

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

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

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

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

Источники: Википедия: Линейный поиск

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

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

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

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

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

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

    public static int LinearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.Length; i++) {
            if (arr[i] == target) return i;
        }
        return -1;
    }

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

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

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

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

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

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

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).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Линейный поиск» чаще всего путают с этими паттернами: Бинарный поиск (массив), Хеш-множество / словарь, Два указателя (в одну сторону), Скользящее окно (переменное) и Элементарные сортировки (выбором, пузырьком, вставками).

• Бинарный поиск (массив) (Binary search (array)): Бинарному поиску нужны отсортированные данные, зато он платит log n. Перебор читает что угодно.
• Хеш-множество / словарь (Hash set / map): Словарь отвечает мгновенно, но его надо сначала построить. Ради одного поиска перебор дешевле.
• Два указателя (в одну сторону) (Two pointers (same direction)): Та пара переписывает массив прямо во время прохода. Поиск только читает.
• Скользящее окно (переменное) (Sliding window (variable)): Окно несёт описание живого отрезка. Перебор несёт максимум лучшее из увиденного.
• Элементарные сортировки (выбором, пузырьком, вставками) (Elementary sorts (selection, bubble, insertion)): Сортировка стоит O(n log n) и окупается при многих поисках. Один поиск её не окупает.

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

• Перебирают внутри другого цикла

  Перебор на каждый элемент превращает O(n) в O(n в квадрате). Постройте словарь один раз.

• Возвращают значение вместо индекса

  Такие задачи почти всегда просят позицию. Значение не скажет, где оно нашлось.

• Забывают случай без совпадения

  Цикл, дошедший до конца, всё равно обязан что-то вернуть. Выберите минус один и держитесь его.

• Перебирают уже отсортированные данные

  На отсортированном входе бинарный поиск куда дешевле. Проверьте вход до написания цикла.

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

Паттерн «Линейный поиск» решает такие задачи с собеседований: Линейный поиск, Первый неповторяющийся символ, Поиск максимума, Есть ли дубликаты на крошечном входе, Пропущенное число, Все индексы значения и Мажоритарный элемент.

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

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

У паттерна «Линейный поиск» целевая сложность O(n).

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