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

O(n log(range))

Ищем бинарным поиском не индекс в массиве, а диапазон возможных ответов: угадываем значение, проверяем его за O(n) и сужаем диапазон по результату проверки.

Сигналы

минимизировать максимум / максимизировать минимумнаименьшее значение, удовлетворяющее условиюнайти наименьшую вместимость/скорость/число дней, которое подходитответ лежит в числовом диапазоне, а не в позиции массивапроверка выполнимости монотонна (становится true после некоторой точки)

Шаблон

function smallestFeasible(lo, hi, canDo) {
    while (lo < hi) {
        const mid = lo + ((hi - lo) >> 1);
        if (canDo(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
// canDo(x) must be monotonic: false...false, true...true

Похоже, но не то

Бинарный поиск (массив): Бинарный поиск по массиву находит значение, которое уже лежит в отсортированном массиве. Здесь массива для индексации нет: бинарный поиск идёт по диапазону возможных ОТВЕТОВ, а каждая догадка проверяется отдельной функцией выполнимости.

диапазон ответов до ~1e9, проверка за O(n) на каждую догадку, монотонная выполнимость -> O(n log(диапазон)) время. Фраза «минимизировать максимум» или «наименьшее x, которое подходит» на большом диапазоне - сигнал, а не размер самого массива.

Изучить этот паттерн