Линейный поиск - Linear search

Линейный поиск
Класс Алгоритм поиска
Наихудшая производительность О ( п )
Лучшая производительность О (1)
Средняя производительность O ( п / 2 )
Сложность пространства в наихудшем случае O (1) итеративный

В информатике , линейный поиск или последовательный поиск представляет собой метод для нахождения элемента в списке . Он последовательно проверяет каждый элемент списка, пока не будет найдено совпадение или пока не будет выполнен поиск по всему списку.

Линейный поиск выполняется в худшем случае за линейное время и выполняет не более n сравнений, где n - длина списка. Если вероятность поиска каждого элемента одинакова, то линейный поиск имеет средний случай п + 1/2сравнений, но средний случай может быть изменен, если вероятности поиска для каждого элемента различаются. Линейный поиск редко бывает практичным, потому что другие алгоритмы и схемы поиска, такие как алгоритм двоичного поиска и хэш-таблицы , позволяют значительно быстрее искать все, кроме коротких списков.

Алгоритм

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

Базовый алгоритм

Учитывая список L из п элементов со значениями или записями L 0 .... L п -1 , и целевым значением Т , следующие подпрограммы используют линейный поиск , чтобы найти индекс мишени T в L .

  1. Установите i в 0.
  2. Если L i = T , поиск завершается успешно; вернуться я .
  3. Увеличьте i на 1.
  4. Если i < n , переходите к шагу 2. В противном случае поиск завершается неудачно.

Со стражем

Базовый алгоритм, приведенный выше, выполняет два сравнения за итерацию: одно для проверки, равно ли L i T , а другое - для проверки, указывает ли я на действительный индекс списка. Добавив в список дополнительную запись L n ( контрольное значение ), которая равна цели, второе сравнение можно исключить до конца поиска, что ускорит алгоритм. Поиск достигнет дозорного, если цель не содержится в списке.

  1. Установите i в 0.
  2. Если L i = T , перейдите к шагу 4.
  3. Увеличьте i на 1 и перейдите к шагу 2.
  4. Если i < n , поиск завершается успешно; вернуться я . В противном случае поиск завершается неудачно.

В упорядоченном столе

Если список упорядочен так, что L 0L 1 ... ≤ L n -1 , поиск может быстрее установить отсутствие цели, завершив поиск, когда L i превышает цель. Этот вариант требует, чтобы дозорный больше, чем цель.

  1. Установите i в 0.
  2. Если L iT , перейдите к шагу 4.
  3. Увеличьте i на 1 и перейдите к шагу 2.
  4. Если L i = T , поиск завершается успешно; вернуться я . В противном случае поиск завершается неудачно.

Анализ

Для списка из n элементов лучший случай - это когда значение равно первому элементу списка, и в этом случае требуется только одно сравнение. В худшем случае значение отсутствует в списке (или встречается только один раз в конце списка), и в этом случае необходимо n сравнений.

Если искомое значение встречается в списке k раз и все упорядочения списка одинаково вероятны, ожидаемое количество сравнений равно

Например, если искомое значение встречается в списке один раз и все упорядочения списка одинаково вероятны, ожидаемое количество сравнений равно . Однако, если известно, что это происходит один раз, то требуется не более n - 1 сравнений, и ожидаемое количество сравнений равно

(например, для n = 2 это 1, что соответствует единственной конструкции if-then-else).

В любом случае, асимптотически стоимость наихудшего случая и ожидаемая стоимость линейного поиска равны O ( n ).

Неравномерные вероятности

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

В частности, когда элементы списка расположены в порядке убывания вероятности и эти вероятности распределены геометрически , стоимость линейного поиска составляет всего O (1).

заявка

Линейный поиск обычно очень прост в реализации и практичен, когда в списке всего несколько элементов или при выполнении одного поиска в неупорядоченном списке.

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

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

Смотрите также

использованная литература

Цитаты

Работает