C++ Binary Search O(nlogn)


  • 0
    J

    We are searching a value while we already know the upper bound and lower bound: the min element and max element.
    The only problem left is how to judge whether we can reach an subarray average larger or equal to the mid.
    Then we can minus this mid value to each element in this array, the problem becomes whether we can find a subarray longer than k , while sum is non-negative.

    bool canReach(vector<int>& nums, double &mid, int &k){
            // build the prefixSum array
            vector<double> prefixSum(nums.size()+1);
            for(int i = 1; i < prefixSum.size(); ++i)
                prefixSum[i] = prefixSum[i-1] + (double)nums[i-1] - mid;           
            // search in this array
            double preMin = 0.0;
            for(int i = k; i < prefixSum.size(); ++i){
                if(prefixSum[i] > preMin) return true;
                preMin = min(preMin, prefixSum[i-k+1]);
            }
            return false;
        }
        
        double findMaxAverage(vector<int>& nums, int k) {
            int minV = INT_MAX, maxV = INT_MIN, n = nums.size();
            for(int &i : nums){
                minV = min(minV, i);
                maxV = max(maxV, i);
            }
            double l = (double)minV, r = (double)maxV;
            
            // binary search
            while(r - l > 10e-6){
                double mid = l + (r-l)/2;
                if(canReach(nums, mid, k)) l = mid;
                else r = mid;
            }
            return (l + r)/2;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.