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

Линейный поиск — это то, что вы делаете, когда ищете имя в неотсортированном списке: начинаете сверху и читаете вниз, пока не найдёте. Это самый простой поиск из всех, он работает с любым списком, а для коротких списков его часто вполне достаточно.

Столбики списка, проверяемые по одному с начала: проверенные столбики потускнели, пунктирная линия на высоте искомого значения, совпавший столбик выделен
Столбики списка, проверяемые по одному с начала: проверенные столбики потускнели, пунктирная линия на высоте искомого значения, совпавший столбик выделен

Идея

Сравните искомое значение с первым значением списка. Если они равны, остановитесь: искомое значение на позиции 1. Иначе сравните его со вторым значением, затем с третьим и так далее. Если и последнее значение не совпало, искомого значения в списке нет. Заранее ничего о списке знать не нужно: он не обязан быть отсортированным, а значения могут быть любыми, лишь бы их можно было сравнить на равенство.

Пример

Ищем 4 в списке 5, 1, 4, 2, 8. Равно ли 5 числу 4? Нет. А 1? Нет. А 4? Да: найдено на позиции 3 после 3 сравнений. Теперь ищем 7 в том же списке. Проверяются все пять значений, и ни одно не совпадает, поэтому после 5 сравнений ответ: 7 в списке нет.

Сколько сравнений

Чтобы найти значение на позиции k, нужно k сравнений. Если искомое значение с равной вероятностью может быть на любой позиции, в среднем это (n + 1)/2 сравнений: 20,5 для 40 значений. Отсутствующее значение всегда требует n, потому что только после последнего сравнения точно известно, что ни одно значение не совпало. Значит, затраты растут пропорционально длине списка, что записывается как O(n).

Быстрому поиску нужен порядок

Линейный поиск не может ничего пропустить, ведь в неотсортированном списке любое значение может оказаться где угодно. Когда список отсортирован, сравнение говорит больше, чем «равно или нет»: оно показывает, с какой стороны искомое значение. Двоичный поиск использует это, чтобы на каждом шаге делить список пополам, и ему нужно около log₂ n сравнений, не больше 6 для 40 значений. Но сортировка тоже требует времени, поэтому для списка, в котором ищут лишь один раз, линейный поиск часто оказывается лучшим выбором.

Небольшие улучшения

Вариант с барьером перед поиском ставит искомое значение в конец списка, так что циклу нужно проверять только совпадение, а не ещё и конец списка. Если при каждой находке сдвигать значение на одну позицию вперёд или в самое начало, часто искомые значения со временем находятся быстрее. Ни то ни другое не меняет худший случай в n сравнений.

Попробуйте сами

Откройте приложение, выберите значение в поле «Искать» и нажмите «Шаг». Пунктирная линия показывает высоту искомого значения, каждое значение выделяется при проверке и тускнеет, когда исключено, а совпадение становится зелёным. Ищите значение, которого нет в списке, чтобы увидеть полный проход, или отключите «Остановиться на первом совпадении» и выберите мало разных значений, чтобы найти несколько совпадений.

Часто задаваемые вопросы

Какова временная сложность линейного поиска?

O(n) в худшем и среднем случае и O(1) в лучшем, когда искомое значение первое. Дополнительная память не нужна.

Чем линейный поиск отличается от двоичного?

Линейный поиск проверяет каждое значение по порядку и работает с любым списком. Двоичный поиск работает только с отсортированным списком, но на каждом шаге делит пополам часть, где может быть искомое значение, поэтому ему нужно около log₂ n сравнений вместо максимум n.

Нужен ли линейному поиску отсортированный список?

Нет. В этом его главное преимущество. В отсортированном списке он может остановиться, как только пройдёт позицию, где было бы искомое значение, но всё равно он медленнее двоичного поиска.

Где применяется линейный поиск?

Везде, где списки короткие или неотсортированные: поиск элемента в небольшом массиве, просмотр файла или потока, который можно читать только по порядку, проверка каждого элемента на условие. Многие библиотечные функции, например indexOf в JavaScript и list.index в Python, — это линейный поиск.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

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