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

Иногда искать нужно не в массиве

Бинарный поиск применим к любому упорядоченному пространству вариантов, если для кандидата можно проверить условие и по результату понять, в какой стороне находится ответ. Частый случай — найти минимальное значение, для которого некоторое условие уже выполняется.

Представим задачу: есть несколько объёмов работы, и мы хотим найти минимальную производительность speed, при которой всю работу можно завершить не более чем за limit единиц времени. Чем больше скорость, тем легче уложиться в лимит. Значит, ответы имеют форму «не подходит, не подходит, ..., подходит, подходит».

Ищем первый подходящий ответ

static int minSpeed(int[] work, int limit) {
    int left = 1;
    int right = Arrays.stream(work).max().orElse(1);

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (canFinish(work, limit, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

static boolean canFinish(int[] work, int limit, int speed) {
    long time = 0;

    for (int amount : work) {
        time += (amount + speed - 1L) / speed;
    }

    return time <= limit;
}

Функция canFinish — это проверка кандидата. Если скорость mid уже подходит, ответ может быть равен ей или быть меньше, поэтому сохраняем середину через right = mid. Если не подходит, все меньшие скорости тоже бесполезны и можно перейти к mid + 1.

Главное условие — монотонность

Бинарный поиск по ответу работает, когда результат проверки меняется в одном направлении: например, сначала все кандидаты дают false, а после некоторой границы — true. Если подходящие и неподходящие варианты хаотично чередуются, отбросить половину диапазона нельзя.

Стоимость зависит от проверки

Если диапазон ответов имеет размер R, бинарный поиск выполнит O(log R) проверок. Если одна проверка canFinish проходит по n элементам, общая сложность будет O(n log R).