{ "type": "doc", "content": [ { "type": "heading", "attrs": { "level": 2 }, "content": [{ "type": "text", "text": "Короткий ответ" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Бинарный поиск — это алгоритм поиска по отсортированным данным, который на каждом шаге делит диапазон пополам и отбрасывает половину. Благодаря этому он работает за O(log n) времени и O(1) памяти (в итеративной форме). Применим к массивам/интервалам, где выполняется монотонность: все «меньше цели» идут до всех «не меньше цели»." } ] }, { "type": "heading", "attrs": { "level": 2 }, "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": "Данные отсортированы (или объект задачи задаёт монотонный предикат: при увеличении индекса/параметра условие не переходит из true обратно в false)." }] }] }, { "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": "orderedList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Выбираем границы диапазона: lo и hi." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Находим середину mid = lo + floor((hi - lo) / 2)." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Сравниваем arr[mid] с целью и отбрасываем половину: либо сдвигаем lo, либо hi." }] }] }, { "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": "Время: O(log n)." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Память: O(1) для итеративной версии; O(log n) для рекурсивной из-за стека." }] }] } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Базовая реализация (итеративная, JS)" }] }, { "type": "codeBlock", "attrs": { "language": "js" }, "content": [ { "type": "text", "text": "function binarySearch(arr, x) {\n let lo = 0;\n let hi = arr.length - 1;\n\n while (lo <= hi) {\n // Безопасная середина без переполнения и без 32-битного сдвига\n const mid = lo + Math.floor((hi - lo) / 2);\n\n if (arr[mid] === x) return mid;\n if (arr[mid] < x) lo = mid + 1;\n else hi = mid - 1;\n }\n\n return -1; // не найден\n}\n\n// Пример\nconst a = [1, 3, 4, 7, 9, 12, 18];\nconsole.log(binarySearch(a, 7)); // 3\nconsole.log(binarySearch(a, 8)); // -1" } ] }, { "type": "paragraph", "content": [ { "type": "text", "text": "В JavaScript числа — 64-битные с плавающей точкой, поэтому классического переполнения как в Java/C++ нет. Но битовые сдвиги приводят к 32-битному целому, что может быть нежелательно на очень больших индексах, поэтому используйте Math.floor((hi - lo) / 2)." } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Первая/последняя позиция и индекс вставки" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Часто нужно найти не «какой-нибудь» индекс равного элемента, а левую/правую границу или позицию для вставки." } ] }, { "type": "codeBlock", "attrs": { "language": "js" }, "content": [ { "type": "text", "text": "// lowerBound: первая позиция, где элемент >= x (левая граница)\nfunction lowerBound(arr, x) {\n let lo = 0, hi = arr.length; // полуинтервал [lo, hi)\n while (lo < hi) {\n const mid = lo + Math.floor((hi - lo) / 2);\n if (arr[mid] < x) lo = mid + 1;\n else hi = mid;\n }\n return lo;\n}\n\n// upperBound: первая позиция, где элемент > x (правая граница + 1)\nfunction upperBound(arr, x) {\n let lo = 0, hi = arr.length;\n while (lo < hi) {\n const mid = lo + Math.floor((hi - lo) / 2);\n if (arr[mid] <= x) lo = mid + 1;\n else hi = mid;\n }\n return lo;\n}\n\n// Диапазон всех вхождений x\nfunction searchRange(arr, x) {\n const first = lowerBound(arr, x);\n const lastExclusive = upperBound(arr, x);\n return first === lastExclusive ? [-1, -1] : [first, lastExclusive - 1];\n}\n\n// Пример\nconst b = [1, 2, 2, 2, 3, 5];\nconsole.log(lowerBound(b, 2)); // 1\nconsole.log(upperBound(b, 2)); // 4\nconsole.log(searchRange(b, 2)); // [1, 3]\nconsole.log(lowerBound(b, 4)); // 5 — индекс вставки для 4" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Поиск по предикату (двоичный поиск по ответу)" }] }, { "type": "paragraph", "content": [ { "type": "text", "text": "Если есть монотонный предикат pred(i), можно найти минимальный i, для которого pred(i) истинно. Это полезно для задач оптимизации по параметру." } ] }, { "type": "codeBlock", "attrs": { "language": "js" }, "content": [ { "type": "text", "text": "function firstTrue(lo, hi, pred) {\n // Возвращает минимальный i из [lo, hi], где pred(i) === true,\n // или hi + 1, если истинных значений нет\n let ans = hi + 1;\n while (lo <= hi) {\n const mid = lo + Math.floor((hi - lo) / 2);\n if (pred(mid)) {\n ans = mid;\n hi = mid - 1; // сужаем вправо к первому true\n } else {\n lo = mid + 1; // сдвигаем в сторону true\n }\n }\n return ans;\n}\n\n// Пример: минимальное n, при котором n*n >= target\nconst target = 50;\nconst i = firstTrue(0, 100, (n) => n * n >= target);\nconsole.log(i); // 8, т.к. 7*7=49 < 50, 8*8=64 >= 50" } ] }, { "type": "heading", "attrs": { "level": 3 }, "content": [{ "type": "text", "text": "Инварианты и частые ошибки" }] }, { "type": "bulletList", "content": [ { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Границы и полуинтервалы: для поиска индекса удобно использовать [lo, hi] и условие цикла lo <= hi; для lower/upperBound — полуинтервал [lo, hi) и условие lo < hi." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Середина: вычисляйте mid как lo + floor((hi - lo) / 2), чтобы избегать переполнений и сохранять прогресс." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Дубликаты: базовый вариант возвращает любой индекс совпадения. Для первой/последней позиции используйте lowerBound/upperBound." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Избегайте зацикливания: после сравнения обязательно исключайте mid из следующего диапазона (lo = mid + 1 или hi = mid - 1 для варианта с [lo, hi])." }] }] }, { "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": "Маленькие массивы, где линейный поиск проще и разницы по времени нет." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Отсутствует произвольный доступ (поток/итератор/связный список)." }] }] }, { "type": "listItem", "content": [{ "type": "paragraph", "content": [{ "type": "text", "text": "Поиск по ключу в неотсортированных структурах — используйте Map/Set. Бинарный поиск нужен именно на отсортированных последовательностях." }] }] } ] } ] }

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

Комментарии