Линейный поиск (Linear search)
Линейный поиск — алгоритм поиска в неупорядоченном массиве или связанном списке.
Алгоритм может использоваться для:
- Проверки наличия элемента в коллекции
- Поиска индекса элемента в коллекции
- Поиска элемента в коллекции по определённому признаку
Псевдокод
Алгоритм линейного поиска предельно прост: последовательно перебираем элементы коллекции пока не найден нужный элемент. Если элемент не найден, то возвращаем признак его отсутствия. Так как индексом элемента может быть только натуральное число, то, обычно, в качестве признака отсутствия элемента в коллекции, функция линейного поиска возвращает число -1.
алгоритм линейный_поиск(последовательность, искомый_элемент)
начало
для каждого элемента в последовательности
если элемент равен искомомый_элемент
то возвращаем индекс элемента и завершаем алгоритм
возвращаем -1
конец
Пример на Python
def linear_search(lst, element):
for i, item in enumerate(lst):
if item == element:
return i
return -1
Требования
Для линейного поиска нет особых требований к входным данным. Произвольный доступ для входной коллекции не обязателен, сортировка тоже не требуется.
Варианты алгоритма
Для определения искомого элемента может использоваться не только простое сравнение но и любое другое условие, например, вместе искомого элемента в функцию линейного поиска может передаваться функция-предикат.
Линейный поиск может искать больше одного элемента, в этом случае лучше использовать filter.
Линейный поиск может применяться для поиска минимального или максимального элемента.
Анализ сложности
Алгоритм выполняет количество действие пропорционально размеру входной коллекции поэтому временная сложность равна .
Потребление памяти не зависит от размера входной коллекции — используется только несколько локальных переменных, поэтому потребление памяти равно .
Связанные алгоритмы
Если массив отсортирован то более эффективно использовать бинарный поиск.