Алгоритмы на Python

Линейный поиск (linear search) в Python

В этом уроке вы реализуете линейный поиск, чтобы найти позицию значения в списке.

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Что такое линейный поиск?

Какую задачу это решает

Иногда данные не отсортированы или в них ищут только один раз: короткий список имён, сегодняшние заказы, первая ошибка в логе. Нужен самый простой поиск, который всегда работает.

Пример из жизни

Линейный поиск похож на поиск ключей в ряду карманов пальто. Вы проверяете первый карман, потом следующий, по одному, и останавливаетесь, как только нашли. Если дошли до последнего кармана, ключей там нет.

От проверки карманов к коду
for index, value in enumerate(values):🧥 Проверять каждый карман по порядку
if value == target:🔑 Ключи здесь?
return index✅ Нашли: прекратить поиск
return -1❌ Проверены все карманы: не найдено
Проверяйте элементы по одному и останавливайтесь на первом совпадении.
Одним предложением

Линейный поиск проверяет элементы коллекции один за другим, пока не найдёт искомое. На это уходит до O(n) шагов, зато сортировка не нужна.

Линейный поиск последовательно проверяет элементы от начала до совпадения или конца списка. Предварительная сортировка данных не требуется.

Как работает алгоритм

  1. Начать с индекса 0.
  2. Сравнить текущий элемент с искомым значением.
  3. При совпадении вернуть индекс, иначе продолжить.
  4. Вернуть -1 после последнего элемента, если совпадения нет.
Сложность: В среднем и худшем случае время O(n), дополнительная память O(1).

Когда это нужно?

  • Несортированные или небольшие коллекции.
  • Разовый поиск, когда сортировать заранее дороже, чем просто перебрать элементы.
  • Поиск первого элемента, подходящего под условие, а не только точного значения.

Когда это не нужно

  • Много поисков в одних и тех же больших данных: отсортируйте их один раз и используйте бинарный поиск или постройте множество (set) или словарь.
  • Нужно только проверить, есть ли значение: target in values делает то же меньшим кодом.

Визуализация: Линейный поиск (linear search) в Python

O(n)

Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.

Пример кода

Запустить код →
main.py
def linear_search(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1

print(linear_search([14, 3, 27, 8, 19], 8))
Получить кнопку запуска для этого примера

Результат выполнения

3

Разбор кода

Функция enumerate() даёт позицию и значение каждого элемента. Как только встречается искомое значение, функция возвращает его позицию, здесь это 3. Если она прошла весь список и ничего не нашла, то возвращает -1. В худшем случае алгоритм проверяет все элементы, поэтому его сложность O(n).

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

return -1 внутри цикла

Функция сдаётся на первом же неподходящем элементе.

Ошибка
for index, value in enumerate(values):
    if value == target:
        return index
    return -1
Исправление
for index, value in enumerate(values):
    if value == target:
        return index
return -1

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи