Leetcode 1283: Find the Smallest Divisor Given a Threshold

https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/description/

Notes:

This question is designed for a binary search!

In general, when can we apply a binary search?  If the target satisfies the following conditions,

1): the target is in a finite range;

2): when the target is <= threshold values, it always true or false;

then we can use a binary search.

For this question, the initial left can be set as 1, and the right can set as 10^6  + 1(why? please think for a while if cannot get it), which represents the range of [left, right).

Then we can check whether the mid = left + (right - left) /2, is the right divider or not.

If it can give a result which is larger than the threshold, it means it is too small and we need to go the range of [mid + 1,   right);

otherwise, we need to go to the range of [left, mid).

See the code below:

class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        int left = 1, right = 1e6 + 1;
        while(left < right) {
            int mid = left + (right - left)/2;
            int ct = 0;
            for(auto &a : nums) {
                ct += a/mid;
                if(a%mid > 0) ++ct;
            }
            if(ct > threshold) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};