Линейный поиск
 |
Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.
|
Линейный, последовательный поиск (также известен как поиск методом полного перебора или в простонародье брутфорса) — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и, в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило, поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.
Если отрезок имеет длину N, то найти решение с точностью до <math>\epsilon</math> можно за время <math>N\over\epsilon</math>. Т.о. асимптотическая сложность алгоритма — <math>O(n)</math>. В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют, только если отрезок поиска содержит очень мало элементов, тем не менее, линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Также линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.
В качестве примера можно рассмотреть поиск значения функции на множестве целых чисел, представленной таблично.
Содержание
Пример
Переменные <math>L</math> и <math>R</math> содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются с первого элемента отрезка. Если искомое значение не равно значению функции в данной точке, то осуществляется переход к следующей точке. То есть в результате каждой проверки область поиска уменьшается на один элемент.
int function LinearSearch (Array A, int L, int R, int Key);
begin
for X = L to R do
if A[X] = Key then
return X
return -1; // элемент не найден
end;
Пример на Swift 3, с "ускоренным" поиском:func linearSearch(element: Int, in array: [Int]) -> Int? {
var array = array
let realLastElement: Int?
if array.isEmpty {
return nil
} else {
realLastElement = array[array.count - 1]
array[array.count - 1] = element
}
var i = 0
while array[i] != element {
i += 1
}
let findedElement = array[i]
if i == array.count - 1 && findedElement != realLastElement {
return nil
} else {
return findedElement
}
}Анализ
Для списка из n элементов лучшим случаем будет тот, при котором искомое значение равно первому элементу списка и требуется только одно сравнение. Худший случай будет тогда, когда значения в списке нет (или оно находится в самом конце списка), в случае чего необходимо n сравнений.
Если искомое значение входит в список k раз и все вхождения равновероятны, то ожидаемое число сравнений
- <math>
\begin{cases}
n & k = 0 \\[5pt]
\displaystyle\frac{n + 1}{k + 1} & 1 \le k \le n.
\end{cases} </math>
Например, если искомое значение встречается в списке один раз, и все вхождения равновероятны, то среднее число сравнений равно <math>\frac{n + 1}2</math>. Однако, если известно, что оно встречается один раз, то достаточно n — 1 сравнений, и среднее число сравнений будет равняться
- <math>\displaystyle\frac{(n + 2)(n-1)}{2n}</math>
(для n = 2 это число равняется 1, что соответствует одной конструкции if-then-else).
В любом случае вычислительная сложность алгоритма O(n).
Приложения
Обычно линейный поиск очень прост в реализации и применим, если список содержит мало элементов, либо в случае одиночного поиска в неупорядоченном списке.
Если предполагается в одном и том же списке большое число раз, то часто имеет смысл предварительной обработки списка, например, сортировки и последующего использования бинарного поиска, либо построения какой-либо эффективной структуры данных для поиска. Частая модификация списка также может оказывать влияние на выбор дальнейших действий, поскольку делает необходимым процесс перестройки структуры.
См. также
Напишите отзыв о статье "Линейный поиск"
Литература
- Дональд Кнут . Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
Отрывок, характеризующий Линейный поиск
Князь Андрей вошел в столовую. Всё общество стояло между двух окон у небольшого стола с закуской. Сперанский в сером фраке с звездой, очевидно в том еще белом жилете и высоком белом галстухе, в которых он был в знаменитом заседании государственного совета, с веселым лицом стоял у стола. Гости окружали его. Магницкий, обращаясь к Михайлу Михайловичу, рассказывал анекдот. Сперанский слушал, вперед смеясь тому, что скажет Магницкий. В то время как князь Андрей вошел в комнату, слова Магницкого опять заглушились смехом. Громко басил Столыпин, пережевывая кусок хлеба с сыром; тихим смехом шипел Жерве, и тонко, отчетливо смеялся Сперанский.Сперанский, всё еще смеясь, подал князю Андрею свою белую, нежную руку.
– Очень рад вас видеть, князь, – сказал он. – Минутку… обратился он к Магницкому, прерывая его рассказ. – У нас нынче уговор: обед удовольствия, и ни слова про дела. – И он опять обратился к рассказчику, и опять засмеялся.
Князь Андрей с удивлением и грустью разочарования слушал его смех и смотрел на смеющегося Сперанского. Это был не Сперанский, а другой человек, казалось князю Андрею. Всё, что прежде таинственно и привлекательно представлялось князю Андрею в Сперанском, вдруг стало ему ясно и непривлекательно.
За столом разговор ни на мгновение не умолкал и состоял как будто бы из собрания смешных анекдотов. Еще Магницкий не успел докончить своего рассказа, как уж кто то другой заявил свою готовность рассказать что то, что было еще смешнее. Анекдоты большею частью касались ежели не самого служебного мира, то лиц служебных. Казалось, что в этом обществе так окончательно было решено ничтожество этих лиц, что единственное отношение к ним могло быть только добродушно комическое. Сперанский рассказал, как на совете сегодняшнего утра на вопрос у глухого сановника о его мнении, сановник этот отвечал, что он того же мнения. Жерве рассказал целое дело о ревизии, замечательное по бессмыслице всех действующих лиц. Столыпин заикаясь вмешался в разговор и с горячностью начал говорить о злоупотреблениях прежнего порядка вещей, угрожая придать разговору серьезный характер. Магницкий стал трунить над горячностью Столыпина, Жерве вставил шутку и разговор принял опять прежнее, веселое направление.
Очевидно, Сперанский после трудов любил отдохнуть и повеселиться в приятельском кружке, и все его гости, понимая его желание, старались веселить его и сами веселиться. Но веселье это казалось князю Андрею тяжелым и невеселым. Тонкий звук голоса Сперанского неприятно поражал его, и неумолкавший смех своей фальшивой нотой почему то оскорблял чувство князя Андрея. Князь Андрей не смеялся и боялся, что он будет тяжел для этого общества. Но никто не замечал его несоответственности общему настроению. Всем было, казалось, очень весело.
Он несколько раз желал вступить в разговор, но всякий раз его слово выбрасывалось вон, как пробка из воды; и он не мог шутить с ними вместе.
Ничего не было дурного или неуместного в том, что они говорили, всё было остроумно и могло бы быть смешно; но чего то, того самого, что составляет соль веселья, не только не было, но они и не знали, что оно бывает.
После обеда дочь Сперанского с своей гувернанткой встали. Сперанский приласкал дочь своей белой рукой, и поцеловал ее. И этот жест показался неестественным князю Андрею.
Мужчины, по английски, остались за столом и за портвейном. В середине начавшегося разговора об испанских делах Наполеона, одобряя которые, все были одного и того же мнения, князь Андрей стал противоречить им. Сперанский улыбнулся и, очевидно желая отклонить разговор от принятого направления, рассказал анекдот, не имеющий отношения к разговору. На несколько мгновений все замолкли.
Посидев за столом, Сперанский закупорил бутылку с вином и сказав: «нынче хорошее винцо в сапожках ходит», отдал слуге и встал. Все встали и также шумно разговаривая пошли в гостиную. Сперанскому подали два конверта, привезенные курьером. Он взял их и прошел в кабинет. Как только он вышел, общее веселье замолкло и гости рассудительно и тихо стали переговариваться друг с другом.
