@zhiqing

I prefer to use: while(l<r) in this case. Then, l will be equal to r in the end. There is no need to worry about l or r will be the required value.

Notice that, when the desired condition is satisfied, I use r=mid. In this case, we will not miss the final value.

Here is my code:

public class Solution {
public int splitArray(int[] nums, int m) {
int max=0;
long sum=0;
for(int num:nums){
max=Math.max(max,num);
sum+=num;
}
long l=max;
long r=sum;
while(l<r){
long mid=l+(r-l)/2;
if(isValid(mid,nums,m)){
r=mid;
}else{
l=mid+1;
}
}
return (int)l;
}
private boolean isValid(long target, int[] nums, int m){
int count=1;
long total=0;
for(int num:nums){
total+=num;
if(total>target){
total=num;
count++;
}
}
return count<=m;
}
}

I think this is similar to a lot of binary search problems, where we are looking for a "boundary" value. In the problem, it is the minimum value which is able to divide the whole array into m non-empty continuous subarrays. There may be many values, which is able to achieve this. We want the minimum one, which is also the largest m among all subarray sums.

For example, we want to find the first number, which is larger or equal to a target value in a sorted array.

The code will be as follows:

int n=nums.length;
int l=0, r=n-1;
while(l<r){
int mid=(r-l)/2+l;
if(nums[mid]>=target){
r=mid;
}else{
l=mid+1;
}
}
return nums[l];

A rule of thumb is to not use mid+1 or mid-1 to update l or r when the desired condition is satisfied. Instead, use mid value to update l or r. If we use mid+1 or mid-1, we may miss the final value. The desired condition is either that the array can be split into at most m non-empty continuous arrays by mid in the split sub-array problem, or that the number at index mid is larger or equal to the target.

Note that the search space in this two problems are different. One is the value, and the other is the index of the value.

Hope this helps!