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

Module 1: Scanline

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

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

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

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

...

Главная/Courses/Course 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);
    }
}