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

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

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

линейный поиск выполняется за линейное время В худшем случае и выполняет не более $n$ сравнений, где $n$ — длина списка. Если каждый элемент будет найден с одинаковой вероятностью, то линейный поиск имеет средний случай $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ n+1 / 2 ⁠$ сравнений, но на средний случай может повлиять, если вероятности поиска для каждого элемента различаются. Линейный поиск редко бывает практичным, поскольку другие алгоритмы и схемы поиска, такие как алгоритм двоичного поиска и хеш-таблицы , позволяют значительно быстрее искать все, кроме коротких списков. ^[2]

Алгоритм

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

Основной алгоритм

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

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

С дозорным ^[4]

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

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

В упорядоченной таблице

Если список упорядочен так, что $L 0 \leq L 1 ... \leq L n -1$ , поиск может установить отсутствие цели быстрее, завершая поиск, как только $L i$ превысит цель. Для этого варианта требуется дозорный, превышающий цель. ^[6]

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

Анализ

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

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

{\begin{cases}n&{\mbox{if }}k=0\\[5pt]\displaystyle {\frac {n+1}{k+1}}&{\mbox{if }}1\leq k\leq n.\end{cases}}

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

\displaystyle {\frac {(n+2)(n-1)}{2n}}

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

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

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

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

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

Приложение

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

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

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

См. также

Ссылки

Цитаты

^ Jump up to: ^а ^б Кнут 1998 , §6.1 («Последовательный поиск»).
^ Кнут 1998 , §6.2 («Поиск путем сравнения ключей»).
^ Кнут 1998 , §6.1 («Последовательный поиск»), подраздел «Алгоритм B».
^ Jump up to: ^а ^б Хорват, Адам. «Бинарный поиск и производительность линейного поиска на платформах .NET и Mono» . Проверено 19 апреля 2013 г.
^ Кнут 1998 , §6.1 («Последовательный поиск»), подраздел «Алгоритм Q».
^ Кнут 1998 , §6.1 («Последовательный поиск»), подраздел «Алгоритм T».
^ Кнут, Дональд (1997). «Раздел 6.1: Последовательный поиск». Сортировка и поиск . Искусство компьютерного программирования. Том. 3 (3-е изд.). Аддисон-Уэсли. стр. 396–408. ISBN 0-201-89685-0 .

Работает

Кнут, Дональд (1998). Сортировка и поиск . Искусство компьютерного программирования . Том. 3 (2-е изд.). Ридинг, Массачусетс: Addison-Wesley Professional. ISBN 0-201-89685-0

[FOOTNOTEKnuth1998§6.1_("Sequential_search")-1] Jump up to: ^а ^б Кнут 1998 , §6.1 («Последовательный поиск»).

[FOOTNOTEKnuth1998§6.2_("Searching_by_Comparison_Of_Keys")-2] Кнут 1998 , §6.2 («Поиск путем сравнения ключей»).

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_B"-3] Кнут 1998 , §6.1 («Последовательный поиск»), подраздел «Алгоритм B».

[:0-4] Jump up to: ^а ^б Хорват, Адам. «Бинарный поиск и производительность линейного поиска на платформах .NET и Mono» . Проверено 19 апреля 2013 г.

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_Q"-5] Кнут 1998 , §6.1 («Последовательный поиск»), подраздел «Алгоритм Q».

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_T"-6] Кнут 1998 , §6.1 («Последовательный поиск»), подраздел «Алгоритм T».

[knuth-7] Кнут, Дональд (1997). «Раздел 6.1: Последовательный поиск». Сортировка и поиск . Искусство компьютерного программирования. Том. 3 (3-е изд.). Аддисон-Уэсли. стр. 396–408. ISBN 0-201-89685-0 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]