Где применяется
1. Задача
До сих пор ты что-то делал с массивами: складывал, двигал окно, строил префиксные суммы. Теперь самый простой вопрос из всех: есть ли значение в списке, и если есть, то где?
Если в списке нет никакого порядка, срезать путь не получится. Нужный элемент может стоять где угодно. Остаётся одно надёжное действие: смотреть ячейки по очереди, пока не найдёшь нужное или пока список не кончится.
У тебя список из 500 записей о пользователях в порядке регистрации, ни по какому полю он не отсортирован. Тебя просят найти пользователя с id 4092. Приходится идти по списку и проверять id каждой записи, пока какой-нибудь не совпадёт.
2. Простыми словами
Вернёмся к 500 пользователям. Тебе нужен id 4092. Ты смотришь первую запись: id 17, не то. Вторую: id 3301, не то. И так дальше по одной. Если запись с id 4092 стоит двадцатой, ты остановишься на двадцатой.
Если такого пользователя нет совсем, ты узнаешь это только в самом конце, когда проверишь все 500 записей. Раньше сказать «нет» нельзя: непроверенная запись могла оказаться той самой.
3. Идея
Иди по списку от первой ячейки к последней. В каждой ячейке сравнивай её значение с искомым. Как только они совпали, останавливайся и возвращай эту позицию. Это и есть ответ.
Если ты дошёл до конца и совпадения не было, значения в списке нет. Возвращай -1, это значит «не найдено». Возвращать нужно позицию первого совпадения: значение может встречаться несколько раз, а обычно нужно первое.
Проследим на [4, 2, 9, 7, 1, 5], ищем 7.
- В ячейке 0 лежит 4, не то.
- В ячейке 1 лежит 2, не то.
- В ячейке 2 лежит 9, не то.
- В ячейке 3 лежит 7, совпало. Возвращаем 3.
Понадобилось четыре проверки. Если бы искали 8, проверили бы все шесть ячеек и вернули -1.
4. Во что это обходится
Время O(n). В худшем случае нужный элемент стоит последним или его нет, и ты проверяешь все n ячеек. В среднем проверяешь около половины. В любом случае работа растёт вместе с длиной списка.
Память O(1). Ты хранишь один счётчик цикла, и ничего, что росло бы вместе с размером входа.
Это цена неупорядоченного списка. Следующие уроки работают с отсортированными данными. В отсортированном списке бинарный поиск находит элемент примерно за log n проверок вместо n. Перебор это честная точка отсчёта, с которой сравнивают все остальные способы.
5. Где это встречается
Array.prototype.indexOf, find и includes в JavaScript, оператор in для списка в Python. Поиск первой подходящей строки в неотсортированном логе или буфере. Поиск настройки в коротком списке, где сортировка обошлась бы дороже, чем сэкономила бы. Любой проход вида «найди первый элемент, у которого выполняется условие X» по данным без полезного порядка.
linearSearch([7, 3, 9, 4, 8, 2], 8)Ищем индекс числа 8. Массив не отсортирован, поэтому остаётся проверять числа по одному с самого начала.
Столбики: отсортированные числа. Обе дорожки ищут число ближе к концу.
Одна операция: одно сравнение с искомым числом. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n)O(log n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- неотсортированный массив
- проверить каждый элемент
- нет гарантии порядка
- найти первое/любое совпадение
- малый 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) и окупается при многих поисках. Один поиск её не окупает.
n примерно до 1e7 даёт O(n) времени и O(1) памяти. Больше или многократно, значит нужна структура.
На LeetCode
Лёгкие задачи, где нужно найти первый элемент, индекс или место, подходящее под условие, в данных без полезного порядка. Иди с начала, остановись на первом совпадении и верни -1, если его нет.
Тот же перебор из урока с другой проверкой i % 10 == nums[i] и -1, если ничего не подошло.
Перебирай слова по порядку и верни первое, которое одинаково читается в обе стороны.
Пробуй каждую стартовую позицию слева направо и верни первую, где совпала needle.
Пройди один раз и остановись на первом месте, где подряд стоят три нечётных числа.
Твоя задача (Tier 1)
Напиши функцию linearSearch(nums, target).
Пройди по списку с начала. Верни позицию первого числа, равного target. Если ни одно число не совпало, верни -1.
- Вход:
nums, список чисел в любом порядке, иtarget, число, которое ищешь. Пример:[4, 2, 9, 7, 1, 5], target7. - Возвращает: позицию первого совпадения или
-1, если совпадений нет.
Шаги:
- Иди по списку слева направо, по одной позиции.
- Если число на этой позиции равно
target, сразу верни эту позицию. - Если дошёл до конца без совпадения, верни
-1.
Готово, когда проходят все тесты:
[4, 2, 9, 7, 1, 5], target7->3(совпадение в середине)[5, 1, 2], target5->0(первое число)[1, 2, 3], target3->2(последнее число)[3, 7, 3, 7], target7->1(вернуть нужно первое совпадение)[1, 2, 3], target9->-1(числа нет в списке)[], target5->-1(пустой список, функция не должна падать)[8], target8->0(одно число, совпадает)[8], target3->-1(одно число, не совпадает)
Практика
linearSearch
linearSearch(nums, target) -> index (0-based) of first match, or -1
export function linearSearch(nums, target) {
// Your code here. The task is described in the box above the editor.
}
Ты здесь как гость
Тесты запускаются прямо здесь, без аккаунта. Код сохраняется только в этом браузере. Бесплатный аккаунт сохранит его на любом устройстве, отметит шаг пройденным и покажет, где ты в курсе.
Лестница подсказок
Застрял? Открывай по одной, но сначала попробуй сам.