What is the time complexity of binary search on the answer?

Worst case O(log(range) × cost of the check). Space complexity is O(1). The predicate must be monotone: once true, true for everything larger.

Binary search on the answer

hard

There is no sorted array here at all. What is sorted is the feasibility check - and a monotone boundary is the only thing binary search actually needs. 'Minimise the maximum' problems all reduce to this.

Worst O(log(range) × cost of the check)Space O(1)

Loading the binary search on the answer engine…

Where to go next

Binary search

easy

Halve the search space with every comparison.

Lower and upper bound

medium

The half-open variant that handles duplicates.

Kadane's algorithm

medium

One decision, repeated n times.