Линейный поиск: Простота и универсальность

Цели урока

• Понять механику линейного поиска и его сложность
• Знать sentinel trick и когда он полезен
• Уметь решать разные задачи поиска (по условию, все вхождения)
• Понимать, когда линейный поиск лучше бинарного

Предварительные знания

• Big O нотация

• Big O: Язык эффективности

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

• **Базы данных** - full table scan при поиске без индекса (аналог линейного поиска)
• **grep в терминале** - ищет по всем строкам файла последовательно
• **Поиск по логам** - однократный поиск конкретного события
• **Связные структуры** - списки, деревья без индексирования

Древнейший поиск и его место у Кнута

У линейного поиска нет одного изобретателя, и это не случайно. Просмотреть всё подряд, пока не найдёшь нужное, люди делали задолго до компьютеров: так листают картотеку, перебирают связку ключей или ищут имя в неотсортированном списке. Это самый естественный алгоритм поиска, и первые программисты переносили его на машины автоматически. Формальное место в науке он получил, когда Дональд Кнут систематизировал поиск в третьем томе The Art of Computer Programming (Sorting and Searching, 1973). Кнут называет его sequential search и подробно разбирает: среднее число сравнений при равновероятных запросах, приём с барьером (sentinel) для устранения проверки границы на каждом шаге, а также вариант с переупорядочиванием по частоте обращений (move-to-front, transpose). Главный его вывод парадоксален: при всей примитивности линейный поиск часто оказывается оптимальным выбором для коротких или редко просматриваемых массивов, где затраты на построение индекса или сортировку не окупаются.

Идея: проверяем всё по порядку

Представь, что ты ищешь ключи в рюкзаке. Ты не знаешь, в каком кармане они лежат. Что делаешь? Открываешь карман за карманом, пока не найдёшь. **Это и есть линейный поиск** - самый естественный способ искать что-то в неупорядоченной коллекции.

**Линейный поиск** проходит по всем элементам массива от начала до конца, проверяя каждый. Как только элемент найден - возвращает его позицию. Если прошли весь массив и не нашли - возвращает -1.

Проследим, как алгоритм ищет число 7 в массиве `[3, 8, 2, 7, 5, 1]`:

В зависимости от того, где окажется нужный элемент, количество шагов сильно отличается:

**Почему average = O(n), а не O(n/2)?** В Big O нотации константы отбрасываются: O(n/2) = O(n). Нас интересует рост, а не конкретные цифры.

Реальные задачи поиска

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

Для критичных по производительности мест существует **sentinel trick** - небольшая оптимизация, которая убирает одну лишнюю проверку на каждой итерации:

**Как работает sentinel:** мы кладём искомый элемент в конец массива. Теперь цикл гарантированно остановится - проверять `i < n` больше не нужно. Это убирает одно сравнение на каждом шаге, что даёт ~30-50% ускорение на больших массивах.

**В Python не стоит писать свой поиск вручную.** Встроенные методы оптимизированы на уровне C и работают быстрее любого Python-цикла: ``` 7 in arr # True/False - проверка наличия arr.index(7) # 3 - найти индекс (ValueError если нет) next((i for i, x in enumerate(arr) if x == 7), -1) # безопасно ```

Когда линейный поиск - правильный выбор

Кажется, что бинарный поиск всегда лучше - он O(log n) против O(n). Но это сравнение нечестное: бинарный поиск требует **отсортированного массива**. Если данные не отсортированы, нужно сначала отсортировать - это O(n log n). После этого бинарный поиск уже не такой выгодный.

**Линейный поиск - правильный выбор в этих ситуациях:**

• Данные **не отсортированы** и сортировать дорого или не нужно
• Массив **маленький** (< 20-50 элементов) - разница не ощутима
• Поиск **одноразовый** - не стоит тратить время на предобработку
• Поиск **по условию** (предикату), а не по конкретному значению
• Данные в **связном списке** - там нет индексного доступа, только перебор

**Классический пример: связный список.** В нём нельзя прыгнуть на середину - только идти по указателям от начала до конца. Бинарный поиск здесь физически невозможен.

**Правило:** если нужно найти что-то один раз в неупорядоченных данных - линейный поиск. Если поиск будет частым - стоит отсортировать данные и использовать бинарный, или добавить хеш-таблицу для O(1) поиска.

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

• O(n) время, O(1) дополнительной памяти
• Работает с любыми данными - сортировка не нужна
• Единственный вариант для связных списков
• Лучше бинарного для одноразового поиска в неотсортированных данных
• Sentinel trick: кладём target в конец, убираем проверку границы
• В Python используй `in`, `.index()` - они быстрее ручного цикла

Следующий шаг

Если данные отсортированы и поиск многократный - есть гораздо более быстрые варианты.

• Бинарный поиск — O(log n) для отсортированных данных
• Хеш-таблицы — O(1) поиск при наличии предобработки

Связанные уроки

• alg-10-binary-search — После линейного поиска следующий шаг - понять, как отсортированность данных даёт O(log n)
• ds-06-hash-intro — Хеш-таблица - следующий уровень: O(1) поиск за счёт предобработки, аналог индекса в БД
• alg-01-big-o — Анализ O(n)/O(1)/O(n/2) и понимание, почему O(n/2)=O(n) требует Big O нотации
• ds-01-arrays