3.9. Binary Search
When doing binary search, there could be multiple elements meeting the condition, or only one, or none. Like the following.
When there are multiple elements meeting the condition, we need to find the first one, or the last one.
Template would be:
while(h<=t){
int m=h+(t-h)/2;
if(condition){
h = m+1;
} else {
t = m-1;
}
}
Naming Convention:
h - head index; t - tail index; T - target
3.9.1. Split Array Largest Sum
Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.
Note: If n is the length of array, assume the following constraints are satisfied: 1 <= n <= 1000, 1 <= m <= min(50, n)
Examples: Input: nums = [7,2,5,10,8], m = 2; Output: 18
Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.
If m and the number of array nums are equal, then each number is a sub-array, so return the largest number in nums. If m is 1, then the entire nums array is a sub-array, return the sum of all numbers in nums.
For other valid m values, the returned value must be between the above two values, so we can use binary search method to do it!
Let’s use an example to analyze: nums = [1, 2, 3 , 4, 5], m = 3. We set left as the maximum value in the array, 5, and right as the sum of numbers 15, and then we figured out that the middle number is 10. What we need to do next is to find the maximum sum and the number of sub-arrays less than or equal to 10, so we get [1, 2, 3, 4], [5]. We can see that this cannot be divided into 3 groups, indicating that the mid is too large, so we let right=mid, and then we do it again. We calculate mid=7, find the number of subarrays with the largest sum less than or equal to 7 again. We get [1,2,3], [4], [5], and we successfully found three groups, indicating that the mid can be further reduced. We let right=mid, and then we perform a binary search again, calculate mid=6, and find the number of sub-arrays whose sum is the largest and less than or equal to 6. We get [1,2,3 ], [4], [5]. We successfully found three groups, we try to continue to reduce the mid. We let right=mid, and then we perform binary search again, calculate mid=5, and find the sum again. The number of subarrays with the largest and less than or equal to 5, [1, 2], [3], [4], [5], found that there are 4 groups, at this time our mid is too small, we should increase the mid, we let left=mid+1, at this time left=6, right=5, the loop exits, we can return left which is 6.
1struct Solution {
2 int split_for_largest_sum(vector<int>& n, int m) {
3 long long int h = *max_element(n.begin(), n.end());
4 long long int t = accumulate(n.begin(), n.end(), 0);
5 while (h <= t) {
6 long long mid = h + (t - h) / 2;
7 if (can_split(n, m, mid))
8 t = mid - 1;
9 else
10 h = mid + 1;
11 }
12 return h;
13 }
14 bool can_split(vector<int>& n, int m, int sum) {
15 int cnt = 1, cs = 0;
16 for (int i = 0; i < n.size(); ++i)
17 if ((cs = cs + n[i]) > sum) {
18 cs = n[i], ++cnt;
19 if (cnt > m) return false;
20 }
21 return true;
22 }
23};
Check Section 2.1.3 for more examples using cumulative sum.
Note
Variant: There is a road, the length is m, and there are k gas stations in the middle (the location of the gas stations is fixed, not evenly distributed). From this we can get the maximum distance between a gas station. Now give you a number t , which represents the number of added new gas stations, find the value that makes the maximum distance between gas stations the smallest, and return the smallest maximum distance. (Hint: BS,Heap)