{ "type": "doc", "content": [ { "type": "heading", "attrs": { "level": 2 }, "content": [ { "type": "text", "text": "Короткий ответ" } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Экспоненциальный поиск (exponential search) — это алгоритм поиска в отсортированном массиве, который сначала экспоненциально расширяет рабочий диапазон (1, 2, 4, 8, ...) до тех пор, пока не «перепрыгнет» целевой элемент, а затем выполняет бинарный поиск внутри найденного диапазона. Время работы — O(log i), где i — позиция искомого элемента; в худшем случае — O(log n). Требует случайного доступа и отсортированности данных." } ] }, { "type": "heading", "attrs": { "level": 2 }, "content": [ { "type": "text", "text": "Подробный разбор" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Идея алгоритма" } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Если массив отсортирован по возрастанию, можно быстро «оценить» примерный диапазон, где может находиться элемент. Для этого мы проверяем индексы, растущие экспоненциально: 1, 2, 4, 8, ... Останавливаемся, когда встретили элемент, не меньший целевого, или вышли за пределы массива. После этого запускаем обычный бинарный поиск внутри этого диапазона." } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Шаги алгоритма" } ] }, { "type": "orderedList", "attrs": { "start": 1 }, "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Проверить первый элемент: если равен цели — вернуть индекс 0." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Инициализировать bound = 1 и удваивать: 1, 2, 4, 8, … пока bound < n и arr[bound] < target." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Определить границы для бинарного поиска: left = bound / 2 (округление вниз), right = min(bound, n - 1)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Выполнить бинарный поиск в [left, right]. Найти индекс или вернуть -1, если элемента нет." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Сложность" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Время: O(log i), где i — индекс цели; в худшем случае O(log n). Экспоненциальный этап — O(log i), бинарный этап — O(log i)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Память: O(1) дополнительной памяти." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Когда применять" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Отсортированные массивы с быстрым случайным доступом (например, обычные массивы в памяти)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Структуры, где длина неизвестна заранее или логически «бесконечна» (например, интерфейсы доступа, возвращающие значение по индексу, но не дающие размер; часто встречается в задачах на собеседованиях)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Сценарии, когда цель предполагается «близко к началу» — экспоненциальный рост быстро локализует небольшой диапазон." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Преимущества и ограничения" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Плюсы: быстрее локализует диапазон по сравнению с линейным поиском; не требует знания длины массива; теоретически может быть эффективнее обычного бинарного, если цель находится близко к началу (меньший логарифм от i, а не от n)." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Минусы: требует отсортированности и случайного доступа; на структуре с дорогим доступом по индексу (например, связные списки) неприменим; при множественных повторениях возвращает произвольный индекс, если не модифицировать бинарный этап для поиска левой границы." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Пример кода (JavaScript)" } ] }, { "type": "codeBlock", "attrs": { "language": "js" }, "content": [ { "type": "text", "text": "function exponentialSearch(arr, target) {\n const n = arr.length;\n if (n === 0) return -1;\n if (arr[0] === target) return 0;\n\n // Экспоненциальное расширение диапазона\n let bound = 1;\n while (bound < n && arr[bound] < target) {\n bound *= 2;\n }\n\n const left = Math.floor(bound / 2);\n const right = Math.min(bound, n - 1);\n return binarySearchInRange(arr, target, left, right);\n}\n\nfunction binarySearchInRange(arr, target, left, right) {\n while (left <= right) {\n const mid = left + ((right - left) >> 1);\n if (arr[mid] === target) return mid; // Для первой позиции см. вариант ниже\n if (arr[mid] < target) left = mid + 1;\n else right = mid - 1;\n }\n return -1;\n}\n\n// Вариант, возвращающий индекс ПЕРВОГО вхождения при дубликатах\nfunction binarySearchFirst(arr, target, left, right) {\n let ans = -1;\n while (left <= right) {\n const mid = left + ((right - left) >> 1);\n if (arr[mid] >= target) {\n if (arr[mid] === target) ans = mid;\n right = mid - 1;\n } else {\n left = mid + 1;\n }\n }\n return ans;\n}\n\n// Пример использования:\n// const idx = exponentialSearch([1,3,5,7,9,12,15,18,21], 12); // => 5" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Пошаговый пример" } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Массив: [1, 3, 5, 7, 9, 12, 15, 18, 21, 24, 27, 30], цель: 18." } ] }, { "type": "orderedList", "attrs": { "start": 1 }, "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Проверяем arr[0] = 1 ≠ 18." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "bound = 1: arr[1] = 3 < 18 → bound = 2." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "bound = 2: arr[2] = 5 < 18 → bound = 4." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "bound = 4: arr[4] = 9 < 18 → bound = 8." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "bound = 8: arr[8] = 21 ≥ 18 → диапазон найден: [left = 4, right = 8]." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Бинарный поиск в [4, 8]: mid = 6 → arr[6] = 15 < 18 → left = 7; mid = 7 → arr[7] = 18 → найдено, индекс 7." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Вариации и практические советы" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Для массивов с дубликатами используйте бинарный поиск левой/правой границы, чтобы вернуть первое/последнее вхождение." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Если порядок убывающий, инвертируйте условия сравнений в обоих этапах." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "При неизвестном размере коллекции используйте безопасный доступ с обработкой выхода за границы (например, API может возвращать +∞/undefined при обращении за пределы). Удваивайте bound до «сигнала» выхода, затем бинарный поиск в последнем валидном диапазоне." } ] } ] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [ { "type": "text", "text": "Проверка краевых случаев" } ] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Пустой массив → вернуть -1." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Цель меньше первого элемента → бинарный этап в узком диапазоне [0, 0]." } ] } ] }, { "type": "listItem", "content": [ { "type": "paragraph", "content": [ { "type": "text", "text": "Цель больше всех элементов → right будет n - 1; бинарный этап корректно вернет -1." } ] } ] } ] } ] }

Что такое экспоненциальный поиск (exponential search)?

Комментарии