что такое линейный поиск

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

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

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

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

Содержание

Пример

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

Анализ

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

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

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

Приложения

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

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

Источник

Алгоритмы поиска в линейных структурах

Таким образом, определим общий алгоритм поиска данных:

Шаг 1. Вычисление элемента, что часто предполагает получение значения элемента, ключа элемента и т.д.

Шаг 2. Сравнение элемента с эталоном или сравнение двух элементов (в зависимости от постановки задачи).

Основные идеи различных алгоритмов поиска сосредоточены в методах перебора и стратегии поиска.

Рассмотрим основные алгоритмы поиска в линейных структурах более подробно.

Последовательный (линейный) поиск

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

Идея этого метода заключается в следующем. Множество элементов просматривается последовательно в некотором порядке, гарантирующем, что будут просмотрены все элементы множества (например, слева направо). Если в ходе просмотра множества будет найден искомый элемент, просмотр прекращается с положительным результатом; если же будет просмотрено все множество, а элемент не будет найден, алгоритм должен выдать отрицательный результат.

Алгоритм последовательного поиска

При наличии в массиве нескольких элементов со значением key данный алгоритм находит только первый из них (с наименьшим индексом).

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

Бинарный (двоичный) поиск

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

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

Алгоритм бинарного поиска

Шаг 3. Если искомое значение больше значения среднего элемента, то возьмем в качестве массива все элементы справа от среднего, иначе возьмем в качестве массива все элементы слева от среднего (в зависимости от характера упорядоченности). Перейдем к Шагу 1.

В массиве может встречаться несколько элементов со значениями, равными ключу. Данный алгоритм находит первый совпавший с ключом элемент, который в порядке следования в массиве может быть ни первым, ни последним среди равных ключу. Например, в массиве чисел 1, 5, 5, 5, 5, 5, 5, 7, 8 с ключом key =5 совпадет элемент с порядковым номером 4, который не относится ни к первому, ни к последнему.

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

Ключевые термины

Бинарный (двоичный, дихотомический) поиск – это поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей.

Ключ поиска – это поле записи, по значению которого происходит поиск

Поиск – это процесс нахождения конкретной информации в ранее созданном множестве данных.

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

Источник

Алгоритм линейного поиска.

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

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

Слово «последовательный» содержит в себе основную идею метода. Начиная с первого, все элементы массива последовательно просматриваются и сравниваются с искомым. Если на каком-то шаге текущий элемент окажется равным искомому, тогда элемент считается найденным, и в качестве результата возвращается номер этого элемента, либо другая информация о нем. (Далее, в качестве выходных данных будет выступать номер элемента). Иначе, следуют возвратить что-то, что может оповестить о его отсутствии в пройденной последовательности.

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

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

Источник

Линейный поиск в C++: подробное руководство

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

Сегодня мы изучим самый простой для реализации алгоритм поиска (но и самый затратный по времени) — линейный поиск.

Как работает линейный поиск

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

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

Как создать линейный поиск

В строке 26 мы предлагаем пользователю с клавиатуры ввести ключ, а дальше мы проверим массив на наличие этого ключа. Если ключ совпал с какой-то ячейкой в массиве, то мы выведем индекс этой ячейки. Это типичный пример чтобы понять как работает алгоритм.

Линейный поиск находится в строках 28 — 32.

Давайте разберем этот пример:

В массиве ans будут храниться все индексы.

Давайте выполним этот код:

А если такого ключа нет в массиве :

Использовать ли линейный поиск

Из плюсов у этого алгоритма только одно — простая реализация.

Минус один, но очень большой — код работает медленно.

Мы советуем использовать его «чайникам» для решения их первых задач. Однако, если вы разрабатываете высоко нагруженное приложение или веб-сервер, такой поиск будет слишком затратным. Вам понадобятся более эффективные алгоритмы. Например, бинарный поиск. Он работает очень быстро и реализация не на много сложнее линейного поиска.

Упражнение

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

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

Источник

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

Python – один из самых популярных и мощных языков. Для выполнения кода требуется несколько строк, что делает его более удобным для пользователя языком. В этом руководстве мы изучим линейный поиск в Python. Поиск – это метод определения того, присутствует ли конкретный элемент в данном списке.

Есть два типа поиска:

Оба метода широко используются для поиска элемента в данном списке.

Что такое линейный поиск?

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

Он сравнивает каждый элемент со значением, которое мы ищем. Если оба совпадают, элемент найден, и алгоритм возвращает позицию индекса ключа.

Концепция линейного поиска

Давайте разберемся в следующих шагах, чтобы найти элемент key = 7 в данном списке.

Шаг – 1: Начните поиск с первого элемента и проверьте ключ = 7 с каждым элементом списка x.

Шаг – 2: Если элемент найден, вернуть индексную позицию ключа.

Шаг – 3: Если элемент не найден, возвращаемого элемента нет.

Алгоритм

Есть список из n элементов и ключевого значения для поиска. Ниже представлен алгоритм линейного поиска.

Программа Python

Давайте разберемся в следующей реализации алгоритма линейного поиска на Python.

Сложность линейного поиска

Временная сложность алгоритма линейного поиска:

Алгоритм линейного поиска подходит для небольшого списка (

Источник