Оптимизация линейного поиска для отсортированного массива Линейный поиск, рассмотренный ранее, проверяет каждый элемент массива, даже если массив отсортирован. Для отсортированного массива (по возрастанию) можно оптимизировать алгоритм, останавливая поиск, как только текущий элемент превышает искомый. Это не меняет асимптотику в худшем случае, но уменьшает количество проверок в среднем. - Применение: - Поиск в отсортированных небольших наборах данных (например, в логе событий, отсортированном по времени). - Предварительный поиск перед использованием более сложных алгоритмов. - Полезно, когда сортировка уже выполнена, но данные редко меняются. - Асимптотика: - Временная сложность: - Лучший случай: O(1)) — элемент найден на первой позиции или первый элемент больше искомого. - Средний случай: O(n/2) — в среднем проверяется половина массива. - Худший случай: O(n) — элемент отсутствует или находится в конце. - Пространственная сложность: O(1) — не требует дополнительной памяти. - Примечание: Если мы ищем число 5 в отсортированном массиве [1, 3, 4, 6, 8], как только мы видим 6, можно остановиться, потому что все последующие элементы больше 5, а значит они нам не нужны. Псевдокод Функция OptimizedLinearSearch(массив A, искомый элемент x): Для каждого индекса i от 0 до длины A - 1: Если A[i] равно x: Вернуть i // Элемент найден Если A[i] больше x: Вернуть -1 // Элемент не найден, дальнейший поиск бессмыслен Вернуть -1 // Элемент не найден Реализация на Python def optimized_linear_search(arr, x): for i in range(len(arr)): if arr[i] == x: return i elif arr[i] > x: return -1 return -1 # Пример использования arr = [1, 3, 4, 6, 8] x = 5 result = optimized_linear_search(arr, x) print(f"Элемент {x} найден на индексе: {result}") # Вывод: Элемент 5 найден на индексе: -1 Пример использования Пример работы Рассмотрим массив A = [1, 3, 4, 6, 8] (отсортирован по возрастанию) и ищем x = 5. 1. i = 0: A[0] = 1 < 5, продолжаем. 2. i = 1: A[1] = 3 < 5, продолжаем. 3. i = 2: A[2] = 4 < 5, продолжаем. 4. i = 3: A[3] = 6 > 5, останавливаемся, возвращаем -1. Результат: Элемент 5 отсутствует, возвращается -1. Теперь ищем x = 4: 1. i = 0: A[0] = 1 < 4, продолжаем. 2. i = 1: A[1] = 3 < 4, продолжаем. 3. i = 2: A[2] = 4 = 4, возвращаем 2. Результат: Элемент 4 найден на индексе 2. Визуализация Индекс: 0 1 2 3 4 Значение:[1, 3, 4, 6, 8] ↑ ↑ x=4 x=5 (остановка) Для x = 5 поиск останавливается на A[3] = 6, так как 6 > 5. Упражнения 1. Простая задача: - Модифицируй код, чтобы он возвращал индекс первого элемента, строго большего x (например, для x = 5 вернуть индекс 3, где A[3] = 6). - Сложность: O(n). 2. Оптимизация: - Реализуй версию, которая ищет все вхождения элемента в отсортированном массиве, используя раннюю остановку (например, для [1, 2, 2, 2, 3] и x = 2 вернуть [1, 2, 3]). 3. Прикладная задача: - Напиши функцию для поиска всех событий в отсортированном логе (список словарей [{"time": 10, "event": "start"}, ...]), где время меньше заданного (например, max_time = 15). Применение: фильтрация логов. 4. Задача с LeetCode: - Search Insert Position (Easy). Задача требует найти позицию для вставки элемента, что связано с нашей оптимизацией.