Бинарный поиск по ответу

Бинарный поиск по ответу

Идея

Иногда мы ищем не элемент в массиве, а наименьший или наибольший ответ, который удовлетворяет условию.

Подход такой:

• перебираем возможный ответ mid;
• проверяем: подходит он или нет;
• если подходит — пробуем сделать ответ лучше;
• если не подходит — ищем дальше.

Главное условие

Должна выполняться монотонность:

• если mid подходит, то все большие (или, в другой постановке, все меньшие) значения тоже подходят;
• если mid не подходит, то все меньшие (или большие) тоже не подходят.

Именно это свойство позволяет применять бинарный поиск по ответу.

Шаблон

Пример задачи

Дано целое число $n$, требуется найти минимальное целое число $x \geq n^2$.