WikiSort.ru - Программирование

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.

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

Если отрезок имеет длину N, то найти решение с точностью до ${\displaystyle \epsilon }$ можно за время ${\displaystyle N \over \epsilon }$ . Т.о. асимптотическая сложность алгоритма — ${\displaystyle O(n)}$ . В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют, только если отрезок поиска содержит очень мало элементов, тем не менее, линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Также линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.

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

Пример

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

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, с "ускоренным" поиском:

 1 func linearSearch(element: Int, in array: [Int]) -> Int? {
 2     var array = array
 3     
 4     let realLastElement: Int?
 5     if array.isEmpty {
 6         return nil
 7     } else {
 8         realLastElement = array[array.count - 1]
 9         array[array.count - 1] = element
10     }
11     
12     var i = 0;
13     while array[i] != element {
14         i += 1;
15     }
16     
17     let findedElement = array[i];
18     if i == array.count - 1 && findedElement != realLastElement {
19         return nil
20     } else {
21         return i
22     }
23 }

Анализ

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

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

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

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

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

(для 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.