Линейный поиск¶
Линейный поиск — алгоритм поиска элемента в массиве (или другом последовательном контейнере), при котором элементы последовательно сравниваются с искомым значением до тех пор, пока совпадение не будет найдено или не будут просмотрены все элементы. Также называется последовательным поиском. Относится к классу простейших алгоритмов и не требует упорядоченности данных. Наиболее распространённая реализация имеет временную сложность O(n) в худшем и среднем случае и O(1) в лучшем случае (если искомый элемент находится первым).
¶Принцип работы
Алгоритм последователен: перебираются элементы массива по порядку — от первого к последнему, от последнего к первому или в произвольном порядке (например, с середины). На каждом шаге текущий элемент сравнивается с искомым значением. При совпадении поиск завершается и возвращается индекс (или указатель) найденного элемента. Если все элементы просмотрены и совпадения нет, возвращается признак отсутствия — обычно −1 или null.
Типичная реализация на псевдокоде:
`` function linearSearch(array, target): for i from 0 to length(array) - 1: if array[i] == target: return i return -1 ``
Алгоритм не изменяет исходный массив и не требует дополнительной памяти — его пространственная сложность O(1).
¶Сложность и эффективность
| Случай | Сравнений (в среднем) | Сложность |
|---|---|---|
| Лучший | 1 | O(1) |
| Средний | n/2 | O(n) |
| Худший | n | O(n) |
Линейный поиск эффективен при работе с небольшими массивами, неупорядоченными данными, однократным проходом по потоку данных или когда стоимость обращения к элементу выше стоимости сравнения. Он не требует предварительной сортировки, что исключает накладные расходы на подготовку данных.
¶Виды линейного поиска
- Прямой линейный поиск — просмотр от начала к концу с возвратом первого найденного совпадения.
- Поиск с конца — просмотр от последнего элемента к первому, возвращает последнее совпадение.
- Интерполируемый линейный поиск — оценка позиции элемента на основе распределения значений (используется в сортировке подсчётом и поиске по распределению).
- Поиск в связном списке — линейный перебор узлов, где доступ к произвольному элементу возможен только последовательно.
¶Сравнение с бинарным поиском
Бинарный поиск работает только с отсортированными массивами и имеет сложность O(log n), что существенно быстрее при больших объёмах данных. Однако для небольших массивов (до нескольких сотен элементов) линейный поиск часто быстрее на практике из-за отсутствия накладных расходов на сортировку и более простой логики сравнений. Компромиссный вариант — интерполяционный поиск, который учитывает распределение значений и работает быстрее на равномерно распределённых данных.
¶Применение
Линейный поиск применяется в следующих случаях:
- Массив небольшого размера (менее 100–1000 элементов).
- Данные не отсортированы, и сортировка экономически нецелесообразна.
- Требуется однократный проход по данным (например, поиск в потоке данных).
- Реализация на языках программирования без встроенной поддержки сложных структур данных.
- Поиск в связных списках, где случайный доступ невозможен.
В языках программирования линейный поиск реализуется в стандартных библиотеках: Array.prototype.find в JavaScript, list.find в Python, std::find в C++.
¶Ограничения
Главный недостаток — линейная зависимость времени выполнения от размера массива. При больших объёмах данных (миллионы элементов) линейный поиск становится неэффективным, и предпочтение отдаётся хеш-таблицам (средняя сложность O(1)) или бинарному поиску (O(log n)). Также алгоритм не оптимален для повторяющихся запросов к одному и тому же массиву — в этом случае предварительная индексация данных окупается.
¶История
Линейный поиск — один из старейших алгоритмов, известный с момента появления вычислительной техники. Он описан в ранних работах по программированию 1950-х годов и остаётся базовым алгоритмом, изучаемым на курсах информатики. В современных системах он используется как эталон для сравнения эффективности более сложных алгоритмов поиска.