В информатике линейный поиск или последовательный поиск — это метод поиска элемента в списке . Он последовательно проверяет каждый элемент списка до тех пор, пока не будет найдено совпадение или пока не будет просмотрен весь список. [ 1]
Линейный поиск выполняется за линейное время в худшем случае и делает максимум n сравнений, где n — длина списка. Если каждый элемент с одинаковой вероятностью будет найден, то линейный поиск имеет средний случай н+1/2 сравнения, но средний случай может быть затронут, если вероятности поиска для каждого элемента различаются. Линейный поиск редко бывает практичным, поскольку другие алгоритмы и схемы поиска, такие как алгоритм бинарного поиска и хэш-таблицы , позволяют значительно быстрее искать для всех списков, кроме коротких. [2]
Линейный поиск последовательно проверяет каждый элемент списка, пока не найдет элемент, соответствующий целевому значению. Если алгоритм достигает конца списка, поиск завершается неудачно. [1]
При наличии списка L из n элементов со значениями или записями L 0 .... L n −1 и целевого значения T следующая подпрограмма использует линейный поиск для нахождения индекса цели T в L . [3]
Базовый алгоритм выше делает два сравнения за итерацию: одно для проверки, равно ли L i T , а другое для проверки, все еще ли i указывает на допустимый индекс списка. Добавив дополнительную запись L n в список ( сигнальное значение ), которое равно цели, второе сравнение можно исключить до конца поиска, что ускорит алгоритм. Поиск достигнет сигнального значения, если цель не содержится в списке. [5]
Если список упорядочен таким образом, что L 0 ≤ L 1 ... ≤ L n −1 , поиск может установить отсутствие цели быстрее, завершив поиск, как только L i превысит цель. Этот вариант требует дозорного, который больше цели. [6]
Для списка с n элементами наилучшим случаем является случай, когда значение равно первому элементу списка, в этом случае требуется только одно сравнение. Наихудшим случаем является случай, когда значение отсутствует в списке (или встречается только один раз в конце списка), в этом случае требуется n сравнений .
Если искомое значение встречается в списке k раз и все упорядочения списка равновероятны, то ожидаемое число сравнений равно
Например, если искомое значение встречается в списке один раз, и все упорядочения списка равновероятны, то ожидаемое количество сравнений равно . Однако, если известно , что оно встречается один раз, то требуется не более n - 1 сравнений, а ожидаемое количество сравнений равно
(например, для n = 2 это 1, что соответствует единственной конструкции if-then-else).
В любом случае, асимптотически стоимость в худшем случае и ожидаемая стоимость линейного поиска составляют O ( n ).
Производительность линейного поиска улучшается, если искомое значение с большей вероятностью будет находиться вблизи начала списка, чем в его конце. Поэтому, если некоторые значения с гораздо большей вероятностью будут искаться, чем другие, желательно поместить их в начало списка.
В частности, когда элементы списка расположены в порядке убывания вероятности, а эти вероятности распределены геометрически , стоимость линейного поиска составляет всего лишь O(1). [7]
Линейный поиск обычно очень прост в реализации и практичен, когда список содержит всего несколько элементов или при выполнении одного поиска в неупорядоченном списке.
Когда в одном списке нужно искать много значений, часто стоит предварительно обработать список, чтобы использовать более быстрый метод. Например, можно отсортировать список и использовать бинарный поиск или построить из него эффективную структуру данных поиска . Если содержимое списка часто меняется, повторная реорганизация может принести больше проблем, чем пользы.
В результате, хотя в теории другие алгоритмы поиска могут быть быстрее линейного поиска (например, бинарный поиск ), на практике даже на массивах среднего размера (около 100 элементов или меньше) может быть нецелесообразно использовать что-либо другое. На больших массивах имеет смысл использовать другие, более быстрые методы поиска, только если данные достаточно велики, поскольку начальное время подготовки (сортировки) данных сопоставимо со многими линейными поисками. [4]
![{\displaystyle {\begin{cases}n&{\mbox{if }}k=0\\[5pt]\displaystyle {\frac {n+1}{k+1}}&{\mbox{if }}1\leq k\leq n.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c31d35edb255baee3eeb7111ce8a1f7d44a3878)
