Some problems ask for the smallest value that works — the slowest speed that still finishes in time, the smallest box that holds everything — and give you no sorted array to search. But if you can check whether one candidate works, and bigger candidates only ever work better, the candidates themselves form a sorted search space: no, no, …, no, yes, yes, …. Binary search finds the first yes. This is binary search on the answer, and it cracks a whole family of medium and hard interview problems.
Find the Smallest Divisor Given a Threshold. Given an array nums and an integer threshold, choose a positive divisor d, divide every value by it rounding up, and add the results. Return the smallest d whose total is at most threshold. (The threshold is at least the array's length, so some divisor always works.)
nums = [1, 2, 5, 9], threshold = 6 -> 5
nums = [44, 22, 33, 11, 1], threshold = 5 -> 44
nums = [21212, 10101, 12121], threshold = 1000000 -> 1Members only · free account
The rest of this lesson, with 6 more sections, 1 drawing, a dry-run simulator and code in JavaScript, Python, Java and C++, opens with a free account.
Not ready yet? The Arrays course is free to read, no account needed.
In the rest of this lesson