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

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

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

• 1 Алгоритм
  • 1.1 Базовый алгоритм
  • 1.2 С дозорным
  • 1.3 В упорядоченной таблице
• 2 Анализ
  • 2.1 Неравномерные вероятности
• 3 Применение
• 4 См. Также
• 5 Ссылки
  • 5.1 Цитаты
  • 5.2 Работает

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

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

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

1. Установить i в 0.
2. Если L i = T, поиск завершается успешно; return i.
3. Увеличить i на 1.
4. If i < n, go to step 2. Otherwise, the search terminates unsuccessfully.

С дозорным

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

1. Установите i в 0.
2. Если L i = T, перейдите к шагу 4.
3. Увеличьте i на 1 и перейдите к шагу 2.
4. Если i < n, the search terminates successfully; return i. Else, the search terminates unsuccessfully.

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

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

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

.

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

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

$\{n,\; если\; k\; =\; 0,\; n\; +\; 1,\; k\; +\; 1,\; если\; 1\; \le \; k\; \le \; n.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{case\}\; n\; \{\backslash \; t\_dv\; \{if\}\}\; k\; =\; 0\; \backslash \backslash \; [5pt]\; \backslash \; displaystyle\; \{\backslash \; frac\; \{n\; +\; 1\}\; \{k\; +\; 1\}\}\; \{\backslash \; t\_dv\; \{if\}\}\; 1\; \backslash \; leq\; k\; \backslash \; leq\; n.\; \backslash \; end\; \{cases\}\}\}$

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

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

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

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

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

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

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

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

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

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

• Тернарный поиск
• Хэш-таблица
• Задача линейного поиска

Цитаты

Работы

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