двоичный поиск

Статьи

SRT Алгоритм Двоичный поиск Находит границу «нет → да» в упорядоченных данных за log₂ n проверок. O(log n) 2 задачи SRT Приём Двоичный поиск по ответу Если проверить ответ легче, чем найти, и проверка монотонна, — ищем ответ делением пополам. O(log D · стоимость проверки) 2 задачи SRT Алгоритм Экспоненциальный поиск Шаги 1, 2, 4, 8, … пока не перескочишь, потом двоичный поиск: когда граница неизвестна или ответ близко. 2⌊log₂ i⌋ + 1 вопрос до позиции i 1 задача SRT Алгоритм Интерполяционный поиск Прикинуть место по значениям на краях: log log n проб на равномерных ключах и до n — на неудобных. ≈ log₂ log₂ n в среднем, n в худшем 1 задача SRT Алгоритм Троичный поиск Вершина унимодальной функции: сравнить две точки и отбросить часть отрезка. И почему золотое сечение лучше. O(log(L/ε)) вычислений функции 2 задачи SRT Алгоритм Timsort Находит готовые упорядоченные куски и сливает их: стек серий, галоп, powersort. O(n log n), на готовых данных O(n) 2 задачи STR Структура данных Суффиксный массив Отсортированные хвосты текста: поиск двоичным поиском, повторы и число разных кусков по соседям. O(n log n) 2 задачи DP Алгоритм Наибольшая возрастающая подпоследовательность Самая длинная растущая цепочка элементов в исходном порядке: пасьянс и двоичный поиск за n log n. O(n log n) 2 задачи DP Приём Динамика по цифрам Счастливые билеты в любом диапазоне за проход по цифрам: 55 252 из миллиона и любой из 10¹⁸ — за миллисекунду. O(D · 10 · S) 2 задачи DP Алгоритм Красивый перенос строк Жадный перенос против всего абзаца сразу: кратчайший путь по местам разрыва, как в TeX. O(n·L) 2 задачи PAR Приём Встреча посередине Перебрать две половины по отдельности и встретиться в отсортированной таблице: 2·2^(n/2) шагов вместо 2ⁿ. O(2^(n/2) · n) 2 задачи NUM~ Алгоритм Бисекция и метод Ньютона Корень уравнения: деление отрезка пополам надёжно, касательные Ньютона — быстро. бисекция — log₂((b − a)/ε) шагов; Ньютон — около log₂ от числа знаков 2 задачи SYS Структура данных Инвертированный индекс и BM25 Словарь «слово → документы, где оно есть»: запрос читает несколько коротких списков вместо всех текстов. O(сумма длин списков слов запроса); «И» галопом — O(m·log(n/m)) 2 задачи TEC Приём Сжатие координат Значения до миллиарда заменить их номерами по порядку — и строить массивы и деревья по номерам. O(n log n) на сжатие 2 задачи

Задачи

Землетрясения в диапазоне Заехать по пути Как растёт список Python Корень k-й степени Курс без откатов Новый сервер в кольце Поправка на сезон Роман за k дней Сжатый список вхождений Сколько стоит рассрочка Станции проката В одном предложении Два частотных словаря Две лиги поровну Карта на всех масштабах Коробки-матрёшки Параллельные пары Порог плотности Разрез по меридиану Ровный заголовок Самый длинный общий кусок Топ по частям Тренд по любому окну Никто не едет далеко

Часто рядом

классика 10 собеседования 8 олимпиады 7 поиск 6 сортировка 4 массив 3 жадность 3 оптимизация 3 сжатие 3 поисковики 3 в проде 3 динамика 3