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

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

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

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

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

Если конец наступил без совпадения, сообщите о неудаче. Обычно возвращают минус один или 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 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;
}

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

Эти формулировки в условии ведут сюда:

• •неотсортированный массив
• •проверить каждый элемент
• •нет гарантии порядка
• •найти первое/любое совпадение
• •малый 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) памяти. Больше или многократно, значит нужна структура.