Линейный поиск: различия между версиями

викификация, удалил сслыку на algolist (не нашел упоминания этого поиска там)
[непроверенная версия][отпатрулированная версия]
м (Интервики (всего 20) перенесены на Викиданные, d:q787903)
(викификация, удалил сслыку на algolist (не нашел упоминания этого поиска там))
 
== Пример ==
[[переменная (программирование)|Переменные]] <math>L</math> и <math>R</math> содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются с первого элемента отрезка. Если искомое значение не равно значению функции в данной точке, то осуществляется переход к следующей точке. Т.е.То есть, в результате каждой проверки область поиска уменьшается на один элемент.
 
<pre>
end;
</pre>
 
 
== Анализ ==
Если искомое значение входит в список ''k'' раз и все вхождения равновероятны, то ожидаемое число сравнений
 
: <math>
\begin{cases}
n & k = 0 \\[5pt]
</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» большое и «o» малое|O]](''n'').
 
 
== Приложения ==
Обычно линейный поиск очень прост в реализации и применим, если список содержит мало элементов, либо в случае одиночного поиска в неупорядоченном списке.
 
Если предполагается в одном и том же списке большое число раз, то часто имеет смысл предварительной обработки списка, например [[Алгоритм сортировки|сортировки]] и последующего использования [[Бинарный поиск|бинарного поиска]], либо построения какой-либо эффективной структуры данных для поиска. Частая модификация списка также может оказывать влияние на выбор дальнейших действий, поскольку делает необходимым процесс перестройки структуры.
 
== См. также ==
* [[Двоичный поиск]]
* [[Метод дихотомии]]
* [[Метод золотого сечения]]
* [[Троичный поиск]]
 
== Литература ==
|isbn= 0-201-89685-0
}}
== См. также ==
* [[Двоичный поиск]]
* [[Метод дихотомии]]
* [[Метод золотого сечения]]
* [[Троичный поиск]]
 
== Ссылки ==
* http://algolist.manual.ru
 
{{math-stub}}
 
[[Категория:Алгоритмы поиска]]