Линейный поиск в Python
Линейный поиск работает и с неотсортированными данными.
Что такое линейный поиск?
Линейный поиск последовательно проверяет элементы от начала до совпадения или конца списка. Предварительная сортировка данных не требуется.
Как работает алгоритм
- Начать с индекса 0.
- Сравнить текущий элемент с искомым значением.
- При совпадении вернуть индекс, иначе продолжить.
- Вернуть -1 после последнего элемента, если совпадения нет.
Сложность: В среднем и худшем случае время O(n), дополнительная память O(1).
Визуализация: Линейный поиск в 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Как это работает
Каждый элемент сравнивается не более раза: время O(n), память O(1).
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Практические задания
Изменяйте входные данные и проверяйте граничные случаи перед работой с большими наборами.
- Проверьте пустой ввод, один элемент и дубликаты.
- Выводите состояние после каждого шага.
- Сравните производительность с другим решением.