Алгоритмы для чайников. Линейный поиск Теория Линейный поиск (Linear Search) — это простейший алгоритм поиска элемента в неупорядоченном массиве. Он проверяет каждый элемент по порядку, пока не найдёт целевой элемент или не дойдёт до конца массива. Может применяться для: - Поиска всех совпадений в небольших наборах данных - Анализа логов или записей, где нужно найти все вхождения определенного значения - Задач, где важна простота реализации, а не максимальная производительность Асимптотическая сложность: - Временная сложность: - Лучший случай: O(1) — элемент найден на первой позиции. - Средний случай: O(n/2) — в среднем нужно проверить половину массива. - Худший случай: O(n) — элемент в конце или отсутствует. - Пространственная сложность: O(1) — не требует дополнительной памяти. Временная сложность алгоритма - это характеристика, которая описывает, как быстро увеличивается время выполнения алгоритма при увеличении размера входных данных. --------- Пространственная сложность алгоритма – это количество памяти, необходимое для его выполнения, в зависимости от размера входных данных. Она показывает, как объем используемой памяти увеличивается или уменьшается по мере роста размера входной информации Псевдокод Функция LinearSearch(массив A, искомый элемент x): Для каждого индекса i от 0 до длины A - 1: Если A[i] равно x: Вернуть i // Элемент найден, возвращаем его индекс Вернуть -1 // Элемент не найден Пример Рассмотрим массив A = [3, 1, 4, 1, 5] и ищем элемент x = 4. | Начало |-> Проверяем A[0] = 3 → не равно 4. |-> Проверяем A[1] = 1 → не равно 4. |-> Проверяем A[2] = 4 → найдено! |-> Возвращаем индекс 2. Результат: Индекс элемента 4 равен 2. Реализация 1: def linear_search(arr, x): for i in range(len(arr)): if arr[i] == x: return i Реализация 2: def linear_search(arr, x): for idx, value in enumerate(arr): if value == x: return i # Пример использования arr = [3, 1, 4, 1, 5] x = 4 result = linear_search(arr, x) if result is not None:: print(f"Элемент {x} найден на индексе: {result}") # Вывод: Элемент 4 найден на индексе: 2 else: print("Элемент не найден") Визуализация Представьте массив как последовательность ячеек: Значение:[3, 1, 4, 1, 5] > > * Индекс: 0 1 2 3 4 Линейный поиск проверяет ячейки слева направо: [3] → [1] → [4] (найдено!). Упражнения для закрепления: 1. Простая задача: - Реализуйте линейный поиск на Python, чтобы найти все вхождения элемента в массив (например, для A = [3, 1, 4, 1, 5] и x = 1 вернуть [1, 3]). - Сложность: O(n). 2. Оптимизация: - Модифицируйте алгоритм, чтобы он останавливался, если массив отсортирован по возрастанию и текущий элемент больше искомого. Реализуй и сравни с обычным линейным поиском. 3. Прикладная задача: - Напиши функцию, которая ищет пользователя по имени в списке словарей (например, [{"name": "Alice", "id": 1}, {"name": "Bob", "id": 2}]). Применение: поиск в небольшой базе данных. 4. Задача с LeetCode: - Find the Index of the First Occurrence in a String (Easy). Это аналог линейного поиска для строки. ----------