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

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Линейный поиск»  – Новости  · газеты  · книги  · ученый  · JSTOR (Ноябрь 2010 г.) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

Алгоритм

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

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

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

1. Набор я до 0.
2. Если L_я = Т, поиск завершается успешно; возвращаться я.
3. Увеличивать я Автор: 1.
4. Если я < п, перейдите к шагу 2. В противном случае поиск завершится неудачно.

С часовым

Базовый алгоритм, приведенный выше, выполняет два сравнения за итерацию: одно для проверки того, L_я равно Т, а другой, чтобы проверить, я по-прежнему указывает на действительный индекс списка. Добавив дополнительную запись L_п к списку (a контрольное значение ), равный цели, второе сравнение можно исключить до конца поиска, что ускорит алгоритм. Поиск достигнет дозорного, если цель не содержится в списке.^[4]

1. Набор я до 0.
2. Если L_я = Т, перейдите к шагу 4.
3. Увеличивать я на 1 и перейти к шагу 2.
4. Если я < п, поиск завершается успешно; возвращаться я. Иначе поиск завершается неудачно.

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

Если список упорядочен так, что L₀ ≤ L₁ ... ≤ L_п−1, поиск может быстрее установить отсутствие цели, завершив поиск один раз L_я превышает цель. Этот вариант требует, чтобы дозорный больше, чем цель.^[5]

1. Набор я до 0.
2. Если L_я ≥ Т, перейдите к шагу 4.
3. Увеличивать я на 1 и перейти к шагу 2.
4. Если L_я = Т, поиск завершается успешно; возвращаться я. Иначе поиск завершается неудачно.

Анализ

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

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

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

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

${ Displaystyle Displaystyle { гидроразрыва {(п + 2) (п-1)} {2n}}}$

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

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

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

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

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

Заявление

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

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

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

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

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

Рекомендации

Цитаты

Работает

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