Binary Search on the Answer

Sometimes there is no array to search

Binary search can be applied to any ordered space of candidates when a condition can be checked for one candidate and the result tells us which side contains the answer. A common pattern is finding the minimum value for which some condition has already become true.

Imagine a problem with several amounts of work where we want the minimum speed that lets all work finish within at most limit time units. The larger the speed, the easier it is to meet the limit. So the candidates look like “fails, fails, ..., works, works.”

Searching for the first valid answer

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;
}

The function canFinish checks one candidate. If speed mid already works, the answer may be equal to it or smaller, so the midpoint is preserved with right = mid. If it fails, every smaller speed is useless as well, so we can move to mid + 1.

The key requirement is monotonicity

Binary search on the answer works when the check result changes in one direction: for example, all candidates first produce false, and after some boundary they produce true. If valid and invalid candidates alternate unpredictably, there is no justification for discarding half of the range.

The cost depends on the check

If the answer range has size R, binary search performs O(log R) checks. If one canFinish check scans n elements, the total complexity is O(n log R).