Module 1: Scanline

Обработка строк сканирования / событий

Module 2: Introduction to DP

Введение в Динамическое программирование

Module 3: Number theory

Простые числа и факторизация
Решето Эратосфена

Module 4: Graph traversals

Поиск в глубину (DFS)
Поиск в ширину (BFS)
Проверка на двудольность
Нахождение связанных компонентов
Топологическая сортировка

Module 5: Shortest paths

Алгоритм Дейкстры
Алгоритм Флойда — Уоршелла
Bellman–Ford algorithm

Module 6: Game Theory - Basics

Основы состояний игры

Module 7: Introduction to Geometry

Знаковая площадь треугольника
Basic Geometry
Bonus Geometry Problems

Module 8: Various types of Binary Search

Бинарный поиск по ответу
Бинарный поиск по вещественному ответу
Тернарный поиск
Бинарный поиск степенями двойки

Бинарный поиск степенями двойки - Preparation to IOI Part 2

Главная Курсы Ресурсы Задачи Национальная олимпиада Соревнования Таблица лидеров

...

Главная/Courses/Preparation to IOI Part 2/Module 8: Various types of Binary Search/Бинарный поиск степенями двойки

Бинарный поиск степенями двойки

Бинарный поиск степенями двойки

Идея (самая простая)

Мы строим ответ по битам, начиная с самого большого. На каждом шаге задаём вопрос:

«А можно ли прибавить $2^k$ к текущему ответу?»

Если можно — прибавляем, если нет — идём дальше к меньшему шагу. По сути, мы перебираем биты ответа от старшего к младшему.

Шаблон

long long ans = 0;

for (int i = 60; i >= 0; i--) {
    if (check(ans + (1ll << i))) {
        ans += (1ll << i);
    }
}