Binary Search Java


  • 0
    public int splitArray(int[] nums, int m) {
    	if(nums==null || nums.length==0) return 0;
    	int max = 0;
    	int sum = 0;
    	for(int i: nums) {
    		if(i>max) max = i;
    		sum+=i;
    	}
    	return (int)binarySearch(max,sum,nums,m);
    }
    
    public long binarySearch(long left, long right, int[] nums, int m) {
    	while(left<=right) {
    		long middle = (left+right)/2;
    		if(isValid(middle,nums,m)) {
    			right=middle-1;
    		} else {
    			left=middle+1;
    		}
    	}
    	return left;
    }
    
    public boolean isValid(long targetCap, int[] nums, int m) {
    	int currSum = 0;
    	int partitionsCount = 1;
    	for(int i: nums) {
    		currSum+=i;
    		if(currSum>targetCap) {
    			currSum=i;
    			partitionsCount++;
    			if(partitionsCount>m) return false;
    		}
    	}
    	return true;
    }
    

Log in to reply
 

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