Линейный поиск: различия между версиями
[непроверенная версия] | [непроверенная версия] |
м Remove book title formatting (bot, Task7504919) |
м →Пример |
||
Строка 12: | Строка 12: | ||
int function LinearSearch (Array A, int L, int R, int Key); |
int function LinearSearch (Array A, int L, int R, int Key); |
||
begin |
begin |
||
for X = L to R do |
for X = L to R do |
||
if A[X] = Key then |
if A[X] = Key then |
||
return X |
return X |
||
end; |
|||
return -1; // элемент не найден |
return -1; // элемент не найден |
||
end; |
end; |
Версия от 22:22, 18 ноября 2008
Эту статью необходимо исправить в соответствии с правилом Википедии об оформлении статей. |
Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Даный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева нарпаво, т.е. от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.
Если отрезок имеет длину N, то найти решение с точностью до можно за время . Т.о. асимптотическая сложность алгоритма - . В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Так же, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.
В качестве примера можно рассмотреть поиск значения функции на множестве целых чисел, представленной таблично.
Пример
Переменные и содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются с первого элемента отрезка. Если искомое значение не равно значению функции в данной точке, то осуществляется переход к следующей точке. Т.о., в результате каждой проверки область поиска уменьшается на один элемент.
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;
Ссылки
Литература
- Дональд Кнут . Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
Это заготовка статьи. Помогите Википедии, дополнив её. |