文章目录
-
- 二分模板
-
- 模板1
- 模板2
- 模板3
- 使用二分的时机
- 二分下标系列
-
- 搜索插入位置
-
- 二分
- 在排序数组中查找元素的第一个和最后一个位置
-
- （二分）
- 寻找旋转排序数组中的最小值
-
- （二分）
- 寻找旋转排序数组中的最小值Ⅱ
-
- （二分）
- 搜索旋转排序数组
-
- （朴素二分）
- （粗糙二分）
- 搜索旋转排序数组 ll
-
- （二分）
- （粗糙二分）
- 第一个错误版本
-
- （二分）
- （二分）
- 山脉数组的峰顶索引
-
- （暴力）
- （二分）
- （二分）
- （三分）
- 山脉数组中查找目标值
-
- （二分）
- （三分找峰值+二分找target）
- 二分答案系列
-
- x的平方根
-
- （二分）
- 数的三次方根
-
- （浮点数二分）
- 寻找重复数
-
- （暴力）
- （哈希映射）
- （排序）
- （二分）
- （双指针）
- 转变数组中最接近目标的数组和
-
- (二分1)
- （二分2）
- 判断条件复杂的二分系列
-
- 爱吃香蕉的珂珂
-
- （二分）
- 分割数组的最大值（经典模板题：最大值最小化）
-
- （动规）
- （二分+贪心）
- 在D天内送达包裹的能力
-
- （暴力）
- （二分+贪心）
- 制作m束花所需要的天数
-
- （二分）
- 小张的刷题计划
-
- （二分 + 贪心）
- 总结：最大值最小化
▄█▔▉●
二分模板
模板1
int BinarySearch1(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {//
int mid = l + (r - l) / 2;
if (nums[mid] == target) {//
return mid;
} else if (nums[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return -1;
}
模板2
int BinarySearch2(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) {//
int mid = l + (r - l) / 2;
if (nums[mid] >= target) r = mid;//
else l = mid + 1;
}
if (nums[l] == target) return l;
else return -1;
}
int BinarySearch2(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (nums[mid] <= target) l = mid;
else r = mid - 1;
}
if (nums[l] == target) return l;
else return -1;
}
模板3
int BinarySearch3(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target){
r = mid;
} else {
l = mid;
}
}
if (nums[l] == target) return l;
if (nums[r] == target) return r;
return -1;
}
使用二分的时机
当需要在一个范围内，寻找一个数，并且这个数满足可以将整个数组不重不漏地划分为两段的性质，就可以使用二分。
关键点：
1.题目的答案需要求出的是一个数字
2.需要在一个整体有序或者局部有序的范围内寻找该数字
3.有一个题目的要求划分的依据具有二段性
总结：说白了二分查找只不过是因为数组自身满足有序的这个特殊的性质，所以比顺序查找效率高一点，所以在思考二分的时候，可以先想一想暴力求解是不是可以解出来，然后利用二分提高效率。
二分下标系列
搜索插入位置
二分
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
// 因为排除法最后的结果在[0, nums.size()-1]这个范围内
// 所以如果target要插入在数组的最后就需要特判一下
if (target > nums.back()) return nums.size();
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
};
在排序数组中查找元素的第一个和最后一个位置
（二分）
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.empty()) return {-1, -1};
// 二分相同元素的第一个位置
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (nums[l] != target) return {-1, -1};
int first = l;
// 二分相同元素的最后一个位置
l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r + 1>> 1;
if (nums[mid] <= target) l = mid;
else r = mid - 1;
}
int second = l;
return {first, second};
}
};
寻找旋转排序数组中的最小值
（二分）
class Solution {
public:
int findMin(vector<int>& nums) {
if (nums.back() > nums.front()) return nums[0];
// 二分出第一个小于nums[0]的数字
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] > nums.back()) l = mid + 1;
else r = mid;
}
return nums[l];
}
};
寻找旋转排序数组中的最小值Ⅱ
（二分）
class Solution {
public:
int findMin(vector<int>& nums) {
while (nums[0] == nums.back() && nums.size() > 1) nums.pop_back();
if (nums.back() > nums[0]) return nums[0];
int target = nums[0];// 如果选取nums[0]当做目标的话，就需要特判整个数组是否有序
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] < target) r = mid;
else l = mid + 1;
}
return nums[l];
}
};
搜索旋转排序数组
（朴素二分）
问题：一个无序的数组怎么可以使用二分来求解呢？
一个完全无序的数组是不可以使用二分这样的技巧来求解的，但是本题的无序是在旋转一个有序数组之后才变得无序的，所以这样的无序数组还是在局部上相对有序的。因此可以抓住旋转的转折点，这样无序的数组就被分成两个有序的小数组了，这样就可以使用二分了。
问题：怎么找转折点？
抓住转折点的特点，如果在旋转之后，数组不是原数组的话，在转折点的左右应该分别是最大值和最小值，而在一个旋转数组中找最小值是可以求出来的，所以这样就找到了转折点。
解题方法：在一个数组中找到一个转折点，然后分别在两个局部有序的数组中找target。
class Solution {
public:
// 由于二分最小值需要找<=target的第一个值
// 而二分答案需要找>=target的第一个值，所以需要写两个二分
int BinarySearch(vector<int>& nums, int target, int start, int end) {
int l = start, r = end;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (nums[l] == target) return l;
else return -1;
}
int search(vector<int>& nums, int target) {
// 找到最最小值的下标，这同时也就是两端有序数组的分界点
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] <= nums.back()) r = mid;
else l = mid + 1;
}
// 在两端有序数组上分别二分，然后找出答案
int pos = l;
int leftAns = BinarySearch(nums, target, 0, pos - 1);
int RightAns = BinarySearch(nums, target, pos, nums.size() - 1);
return leftAns == -1 ? RightAns == -1 ? -1 : RightAns : leftAns;
}
};
（粗糙二分）
第二种方法就像第一种方法那么细致地找到一个转折点，然后才开始二分，这种方法就比较粗糙，但是也比较快一点。
第一种方法是求出了转折点，然后二分。其实并没有必要求出转折点，因为数组最多只有两段，所以随便一个数组，一定会落在一段有序的数组上。
解题方法：首先
nums[mid]
跟
nums[l]
和
nums[r]
比较，找到出
nums[mid]
在一段有序的数组上。然后再和
target
比较，将
r
或者
l
定范围。
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = l + r >> 1;
if (nums[mid] == target) return mid;
// 数组的前半部分有序
if (nums[mid] >= nums[l]) {
// target在[l, mid)中
if (nums[mid] > target && target >= nums[l]) r = mid - 1;
else l = mid + 1;
}
// 数组的后半部分有序
if (nums[mid] <= nums[r]) {
// target在(mid, r]中
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}
};
搜索旋转排序数组 ll
本题和上一道题目搜索旋转数组ll有什么区别呢？
区别在于本题中，数组是一个数是按非降序排列的数组，数组中的数值可能会有相同的数字。这就破坏了二分的二段性。
什么叫二段性呢？就是原来可以通过划分数组，使得前半段中的数都
>nums.back()
，后半段中的数都
<= nums.back()
，这样就可以找到旋转数组的转折点，然后将数组划分成为两个有序数组，最后对两段有序数组分别进行二分找
target
。
但是不巧的是，现在如果有了相同的数字出现在数组中，那么可能在找旋转数组中的转折点，前半段数组中的数也
>=nums.back()
，后半段数组中的数也
<=nums.back()
，如果不能将数组划分成两段数组的话，就不能使用二分来找到旋转数组的转折点了。
所以只要把数组中的开头和结尾相同的数字删除掉一端，不就又可以将前后两段数组区分开来了么。所以
while(nums.size() > 1 && nums.back() == nums[0]) nums.pop_back()；
把后面如果相同的数字删掉就可以了。
下面两个版本都是在搜索旋转数组l的基础上加上
while(nums.size() > 1 && nums.back() == nums[0]) nums.pop_back()；
就可了。
（二分）
class Solution {
public:
bool BinarySearch(vector<int>& nums, int l, int r, int target) {
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return nums[l] == target;
}
bool search(vector<int>& nums, int target) {
while (nums.size() > 1 && nums.back() == nums[0]) nums.pop_back();
// 找到<=nums.back()的第一个数
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] <= nums.back()) r = mid;
else l = mid + 1;
}
int pos = l;
// 在两段有序数组中的寻找是否存在target
bool flag1 = BinarySearch(nums, 0, pos - 1, target) ;
bool flag2 = BinarySearch(nums, pos, nums.size() - 1, target);
return flag1 || flag2;
}
};
（粗糙二分）
class Solution {
public:
int search(vector<int>& nums, int target) {
while (nums.size() > 1 && nums.back() == nums[0]) nums.pop_back();
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = l + r >> 1;
if (nums[mid] == target) return true;
// 这里是>=,因为前半段数组中只有一个数字了。如果不加上=的话，可能会错过答案
// 数组的前半部分有序
if (nums[mid] >= nums[l]) {
// target在[l, mid)中
if (nums[mid] > target && target >= nums[l]) r = mid - 1;
else l = mid + 1;
} else {// 数组的后半部分有序
// target在(mid, r]中
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return false;
}
};
第一个错误版本
本题中显然可以将数组中的数分成两段，前面一段全是真，后面一段全是假，所以由二段性就可以想到使用二分。
有两种版本的二分，第一种是找第一个false，第二种是找最后一个true然后+1。
（二分）
class Solution {
public:
int firstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (isBadVersion(mid)) r = mid;// 如果正确就向前缩小范围
else l = mid + 1;
}
return l;
}
};
（二分）
class Solution {
public:
int firstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if(!isBadVersion(mid)) l = mid;
else r = mid - 1;
}
// 防止n=1,bad=1这种特殊的情况，没有进入循环。所以还需要特判一步
return !isBadVersion(r) ? r + 1 : r;
}
};
山脉数组的峰顶索引
（暴力）
第一种方法是暴力，从前往后遍历，当
nums[mid] < nums[mid + 1]
继续，当
nums[mid] > nums[mid + 1]
就停下来。
（二分）
既然是要在数组中找一个数，并且数组被分成了两段，就要考虑是否可以使用二分，在使用二分之前需要考虑数组中的数是否具有【二段性】。
因为前面很多的二分的题目都是有一个
target
或者可以参考的数字，然后以这个数字为基准，然后将数组分成两段。
但是这道题目好像没有一个现成的参考数字给我们，但是不要局限在必须要找一个固定参考数字的思维中，因为二段性只是要求有一个性质可以正好将数组分成两段而已。经过仔细的观察过后，不难发现前半段数组都是递增的，而后半段数组都是递减的，这不就将数组划分成为两段了么。
所以根据这点可以有两种二分，第一种是找第一个开始下降的数字的索引。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& nums) {
int l = 0, r = nums.size() - 2;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] > nums[mid + 1]) r = mid;
else l = mid + 1;
}
return l;
}
};
（二分）
第二种是找最后一个递增的数字的索引。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& nums) {
// 因为nums.size()>=3，所以不用担心不进入while的情况
int l = 0, r = nums.size() - 2;
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums[mid] < nums[mid + 1]) l = mid;
else r = mid - 1;
}
return l + 1;
}
};
（三分）
还有一种方法：三分。一般三分问题可以解决单峰值问题。
三分：将数组分成三段，然后每一次通过派出1/3区间的方法，最后逼近到峰值。
具体做法：将区间分成
[L, mid1]
，
[mid1, mid2]
，
[mid2, R]
。如果
arr[mid1] > nums[mid2]
的话，说明峰值一定不在
[mid2, R]
区间内，所以
R = mid2 - 1
，同理如果
arr[mid2] > arr[mid1]
，峰值一定不在
[L, mid1]
中间，
L = mid1 + 1
。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int l = 0, r = arr.size() - 1;
while (l < r) {
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
if (arr[mid1] > arr[mid2]) {
r = mid2 - 1;
} else {
l = mid1 + 1;
}
}
return l;
}
};
山脉数组中查找目标值
（二分）
本题看起来好像很难，但是其实就是三道题目的组合形式而已。
山脉数组中查找目标值=找峰值索引+在正序数组中找target+在逆序数组中找target
在 山脉数组的峰顶索引 中具体讲解了如何利用二分或者三分寻找峰值的索引，而在正序数组或者逆序数组中找
target
就是二分的基本题型了。
/**
* // This is the MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* class MountainArray {
* public:
* int get(int index);
* int length();
* };
*/
class Solution {
public:
int findInMountainArray(int target, MountainArray &mountainArr) {
int l = 0, r = mountainArr.length() - 2;
while (l < r) {
int mid = l + r >> 1;
if (mountainArr.get(mid) > mountainArr.get(mid + 1)) r = mid;
else l = mid + 1;
}
int MaxIndex = l;// 峰值的索引
// 在数组的[0, MaxIndex]中寻找target
l = 0, r = MaxIndex;
while (l < r) {
int mid = l + r >> 1;
if (mountainArr.get(mid) >= target) r = mid;
else l = mid + 1;
}
if (mountainArr.get(l) == target) return l;
// 如果前半段数组中找不到target
// 就在[MaxIndex+1, mountainArr.length()-1]中寻找target
l = MaxIndex + 1, r = mountainArr.length() - 1;
while (l < r) {
int mid = l + r >> 1;
if (mountainArr.get(mid) <= target) r = mid;
else l = mid + 1;
}
if (mountainArr.get(l) == target) return l;
else return -1;
}
};
（三分找峰值+二分找target）
/**
* // This is the MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* class MountainArray {
* public:
* int get(int index);
* int length();
* };
*/
class Solution {
public:
int findInMountainArray(int target, MountainArray &mountainArr) {
// 三分寻找峰值的索引
int l = 0, r = mountainArr.length() - 1;
while (l < r) {
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
if (mountainArr.get(mid1) > mountainArr.get(mid2)) {
r = mid2 - 1;
} else {
l = mid1 + 1;
}
}
int MaxIndex = l;// 峰值的索引
// 在数组的[0, MaxIndex]中寻找target
l = 0, r = MaxIndex;
while (l < r) {
int mid = l + r >> 1;
if (mountainArr.get(mid) >= target) r = mid;
else l = mid + 1;
}
if (mountainArr.get(l) == target) return l;
// 如果前半段数组中找不到target
// 就在[MaxIndex+1, mountainArr.length()-1]中寻找target
l = MaxIndex + 1, r = mountainArr.length() - 1;
while (l < r) {
int mid = l + r >> 1;
if (mountainArr.get(mid) <= target) r = mid;
else l = mid + 1;
}
if (mountainArr.get(l) == target) return l;
else return -1;
}
};
二分答案系列
x的平方根
（二分）
一个数x的平方根一定在
[0, x]
之间，一看到在一个有序的范围内寻找一个数值就可以联想到二分。但是是否可以使用二分找出一个目标值，还需要判断寻找这个数值的逻辑是否可以将整个范围内的数分成两段。即是否具有二段性。
不难发现，这段范围的数中，所有数的平方要么
>x
，要么
<x
，要么
==x
。所以这就可以不重不漏的将所有的数都考虑到了，所以就可以使用二分。虽然前面这句话看起开很像废话，但是下次遇到更难的题目的时候，也可以用这个思路去判断是否可以用二分解题。
class Solution {
public:
int mySqrt(int x) {
if (x == 0 || x == 1) return x;// 如果是0或者1，就直接返回x
uint64_t l = 0, r = x / 2;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (mid <= x / mid) l = mid;
else r = mid - 1;
}
return l;
}
};
数的三次方根
（浮点数二分）
上面一道题目是整数二分，这道题目是一个浮点数二分，就是在一个范围内寻找一个浮点数。
其实逻辑和整数二分是差不多的。但是要注意的是：因为浮点数的比价不能像整数比较那样，十分明确用
==
来比较两个数的相等性。
因为浮点数的存储的缘故，所以在精度0两个数上永远不可能相等。所以规定在两个数小于某一个很小的数（如
1e-6
）的时候，就判定两个数相等了。
浮点数二分不仅在比较两个数的时候比较特殊，在划定范围的时候也比较特殊。在整数二分的时候因为除法的向下取整和可能数组中有多个相同的数，所以需要控制二分的边界。但是二分浮点数的时候就不用考虑这么多，直接判断，然后要么
l = mid
，要么
r = mid
。因为浮点数在数字中只有一个并且浮点数的除法也没有向下取整的说法。
总结：在浮点数二分的时候，第一需要在两个数比较的时候，拿一个很小的数作参考。第二在缩小范围的时候，不用考虑边界。
#include <iostream>
using namespace std;
#define eps 1e-6
int main()
{
double x;
cin >> x;
double l = -1000, r = 1000;
while ((r - l) >= eps) {
double mid = (r + l) / 2.0;
if (mid * mid * mid <= x) l = mid;
else r = mid;
}
printf("%.6f\n", l);
return 0;
}
寻找重复数
（暴力）
暴力就是将所有的数全部两两比较，中间发现有重复的数字就直接返回该数字。
暴力的方法并没有用到数组中的数全部都在
[1, n]
之间这个特点，所以使用性最强但是也是最慢的。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
for (int i = 0; i < nums.size(); i ++) {
int num = nums[i];
for (int j = i + 1; j < nums.size(); j ++) {
if (num == nums[j]) return num;
}
}
return 0;
}
};
- 时间复杂度O(N2)
- 空间复杂度O(1)
（哈希映射）
因为数组中n+1个数，全部都在
[1, n]
之间，所以本应该是一个萝卜一个坑，但是现在有一个坑位有两个萝卜，先要找出那个多出的萝卜。
这样不难想到可以使用哈希表，将每一个数字都映射到数组中的一个位置上。顺着这个思路，可以遍历这个数组，然后将数字映射到数组中相应的位置上，如果返现该位置上已经有数字了，就返回该重复数字。（也可以使用
unordered_set
哈希表）。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size();
vector<int> cnt(n + 1, 0);
// 将nums[i]放在第nums[i]个位置上
// 如果一个位置被放了两次，就说明该数字为重复数字
for (int i = 0; i < nums.size(); i ++) {
if (cnt[nums[i]] != 0) return nums[i];
cnt[nums[i]] = nums[i];
}
return 0;
}
};
- 时间复杂度O(N)
- 空间复杂度O(N)
（排序）
既然是重复的数字，那么排序之后两个重复的数字一定会紧挨在一起。所以只要排完序之后，找出相邻且相等的元素就是重复的元素。
利用排序算法也没有用到数组中的数都在
[1, n]
之间的特性。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 1; i ++) {
if (nums[i + 1] == nums[i]) return nums[i];
}
return 0;
}
};
- 时间复杂度O(Nlogn)
- 空间复杂度O(1)
（二分）
根据抽屉原理：在10个抽屉中放11个苹果，那么至少有一个抽屉中有2个苹果。
在
[1, n]
的范围中有一个数m，如果在数组
nums
中
<=m
的个数
==m
的话之前的数字，说明是m不是重复的元素。但是如果在数组
nums
中
<=m
的个数
>m
的话，就说明m是重复的元素之后的数字或者m就是重复数字，因为原本
个数==m
但是由于m是重复的元素，所以小于等m的个数会多出一个。
像这样通过个数可以将
[1,n]
分成两段（重复数字之前
个数==m
，重负数字之后或者重复数字
个数>m
），就可以使用二分。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int l = 1, r = nums.size() - 1;// 搜索区间为[1, n(即nums.size() - 1)]
while (l < r) {
int mid = l + r >> 1;
// 统计<= mid的个数
int cnt = 0;
for (int num : nums) {
if (num <= mid) cnt ++;
}
// 缩小范围
if (cnt > mid) r = mid;
else l = mid + 1;
}
return l;
}
};
- 时间复杂度O(Nlogn)
- 空间复杂度O(1)
（双指针）
因为数组中的数字都是在
[1,n]
之间的，所以如果没有重复的数字的话，如果按照
m = nums[m]
这样的逻辑的话，一定会形成一条链表，如
nums={1, 2, 3, 4}
，形成
1->2->3->4
。（这一点很难联想到，可以这么想：因为没有相同数字并且没有数字0（从1开始[1,n]范围内），所以两个数字之间不可能相互指向）。
如果数组中有重复的数字，那么两个数字之间就有可能相互指向，这样就形成了一个闭环的链表，而重复数字就是链表的入环口。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int fast = 0, slow = 0;
while (1) {
fast = nums[nums[fast]];
slow = nums[slow];
if (slow == fast) break;
}
fast = 0;// 从头开始走
while (slow != fast) {
fast = nums[fast];
slow = nums[slow];
}
return fast;
}
};
- 时间复杂度O(N)
- 空间复杂度O(1)
转变数组中最接近目标的数组和
(二分1)
其实本题就是在
[0, max(arr[i])]（max(arr[i])是指arr数组中的最大值）
中寻找一个数
mid
，该数字可以是的数组中的所有
>mid
的数字都变成
mid
，最后可以 使得数组中的和最接近
target
。
本题的难点在于需要找到最接近
target
的数字，而不是找到具体的某一个整数。
如果这题改成找到数组和等于
target
(保证一定有解)，这样你会不会？这就改过之后就变成了一个经典的二分问题了。这就可以直接使用二分，然后在再
check()
函数中判断第一个使得数组和
>=target
的数字。返回即可。
其实写到这里就已经很接近答案了，为什么？因为最接近
target
的数字一定是两个，一个数可以使得数组和
>=target
，一个数可以使得数组和
<=target
。所以如果求出了第一个可以使得数组和
>=target
的数字
left
，那么另一个可以使得数组和最接近
target
的数字就是
left - 1
了。最后比较一下
left
和
left-1
拿一个可以使得数组和更接近
target
就可以了。
class Solution {
public:
int Sum(int mid, vector<int>& arr) {
int sum = 0;
for (int num : arr) sum += min(num, mid);
return sum;
}
int findBestValue(vector<int>& arr, int target) {
int l = 0, r = 0;
for (int n : arr) r = max(r, n);
while (l < r) {
int mid = l + r >> 1;
if (Sum(mid, arr) >= target) r = mid;
else l = mid + 1;
}
int up = Sum(l, arr);
int low = Sum(l - 1, arr);
if (abs(up - target) < abs(target - low)) return l;
else return l - 1;
}
};
（二分2）
当然出来求出第一个使得数组和
>=target
的数。也可以求出最后一个
<=target
的数字
right
，然后比较
right
和
right + 1
哪一个可以使得数组和更接近
target
。
class Solution {
public:
int Sum(int mid, vector<int>& arr) {
int sum = 0;
for (int i = 0; i < arr.size(); i ++) sum += min(arr[i], mid);
return sum;
}
int findBestValue(vector<int>& arr, int target) {
int l = 0, r = 0;
// // 寻找最大值r
for (int n : arr) r = max(r, n);
while (l < r) {
int mid = l + r + 1 >> 1;
if (Sum(mid, arr) <= target) l = mid;
else r = mid - 1;
}
int low = Sum(l, arr);
int up = Sum(l + 1, arr);
if (abs(low - target) <= abs(target - up)) return l;
else return l + 1;
}
};
判断条件复杂的二分系列
爱吃香蕉的珂珂
（二分）
这道题翻译一下就是在一个范围内寻找一个数，该数字使得将所有数抵消掉的次数
<=H
，求出该数字的最小值。
这就很像二分的题目，求出一个数字满足某一个性质。
所以套入二分的模板，发现就是求出时间
<=h
的第一个数。注意本题再求出h的时候有一点绕，因为当
mid
越小的时候花费的时间越长，
mid
越大的时候，花费的时间月小。所以当算出的时间
<=h
的时候，
r = mid
应该缩小右边的范围。
除法的向上取整小技巧：(a + b - 1) / b
class Solution {
public:
int Hour(int mid, vector<int>& piles) {
int cnt = 0;
for (int n : piles) {
cnt += (n + mid - 1) / mid;// n/mid向上取整
}
return cnt;
}
int minEatingSpeed(vector<int>& piles, int h) {
int l = 1, r = 0;// l从1开始，因为除法中除数不能为0
// 范围[1, max(piles[i])]
for (int n : piles) r = max(n, r);
while (l < r) {
int mid = l + r >> 1;
// 找到第一个<=h的数字
// mid越小，时间越大
if (Hour(mid, piles) <= h) r = mid;
else l = mid + 1;
}
return l;
}
};
分割数组的最大值（经典模板题：最大值最小化）
其中非负整数和连续的子数组很重要
（动规）
class Solution {
public:
int splitArray(vector<int>& nums, int m) {
vector<vector<int>> dp(nums.size() + 1, vector<int>(m + 1, INT_MAX));
// 求出前缀和
vector<int> sum(nums.size() + 1, 0);
for (int i = 1; i <= nums.size(); i ++) sum[i] = nums[i - 1] + sum[i - 1];
dp[0][0] = 0;
for (int i = 1; i <= nums.size(); i ++) {// 数组长度
for (int j = 1; j <= m; j ++) {// 分割后子集的个数
for (int k = 0; k < i; k ++) {
dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sum[i] - sum[k]));
}
}
}
return dp[nums.size()][m];
}
};
（二分+贪心）
class Solution {
public:
// 求出数组中最大和不超过maxSum的情况下，nums要被分成几段
int split(vector<int>& nums, int maxSum) {
int subCnt = 1;// 数组中连续集合的个数
int curSum = 0;
for (int num : nums) {
if (curSum + num > maxSum) {
subCnt ++;
curSum = 0;
}
curSum += num;
}
return subCnt;
}
int splitArray(vector<int>& nums, int m) {
int l = 0, r = 0;// l是一个数中的最大值，r是整个数组中的最大值即整个数组的和
int sum = 0;
for (int num : nums) {
l = max(num, l);
sum += num;
}
r = sum;
while (l < r) {
int mid = l + r >> 1;
if (split(nums, mid) <= m) r = mid;
else l = mid + 1;
}
return l;
}
};
在D天内送达包裹的能力
（暴力）
首先可以来想一下暴力方法怎么解？
要求的是在D天内需要送达包裹，需要的最低载重能力。重点在这个最低载重能力上，现在不妨先预估一下载重能力可以去哪些数，如果一天可以载重是无限大，那么无论是多少件物品都可以1天内送达，这个是最大的例子，如果比无限大小一点呢？还是1天内送到。我们发现需要满足D天内的送达的数值原来可以有很多，那么我们就来往小的预估。如果不考虑天数，需要将所有货物送到需要的最低载重能力是多少，不难发现就是所有货物中载重最重的那一个货物，因为如果要将所有的货物送到，每一个货物不可能劈成两半送往，所以要保证将最重的货物送达就需要最低的载重能力为最重货物的重量。
经过上面一分析，最低的载重能力其实就在
[max(weight[i]), 无限大]
，但是这个无限大也可以缩小一点吧。如果所有货物要1天送到，载重能力就是所有货物的重量总和。所以载重能力就是
[max(weights[i]), sum(weights[i])]
因为送货物的顺序必须按照顺序送，也就是数组中的数必须要连续的取用，所以如果给了一个载重能力，就可以算出对应的送货天数。
综上：已经有了总重能力的范围，也可以根据送货的总重算出对应的天数，如此就可以暴力的将所有载重能力算出对应的天数，然后和预期的
days
比较。如果载重能力是正向枚举的，那么第一个满足送货天数
<=days
的载货能力就是最低的载货能力。（days和载货能力成反比，载货能力越强，days越小）
class Solution {
public:
int split(vector<int>& weights, int maxLoad) {
int days = 1;// 送货至少要一天
int curLoad = 0;// 当前的货物载重量
for (int w : weights) {
if (curLoad + w > maxLoad) {// 如果当前数加上之后>maxLoad的话，就说明载重达到上限
days ++;
curLoad = 0;
}
curLoad += w;
}
return days;
}
int shipWithinDays(vector<int>& weights, int days) {
int l = 0, r = 0;
for (int w : weights) {
l = max(l, w);
r += w;
}
for (int i = l; i <= r; i ++) {
if (split(weights, i) <= days) return i;
}
return 0;
}
};
（二分+贪心）
经过暴力方法的分析，可以提炼出从一个范围的数中，寻找出一个数，该数字满足使得送货的天数
<=days
。
所以就可以不用顺序查找了，可以使用二分开解决该问题。
class Solution {
public:
int split(vector<int>& weights, int maxLoad) {
int days = 1;// 送货至少要一天
int curLoad = 0;// 当前的货物载重量
for (int w : weights) {
if (curLoad + w > maxLoad) {// 如果当前数加上之后>maxLoad的话，就说明载重达到上限
curLoad = 0;
days ++;
}
curLoad += w;
}
return days;
}
int shipWithinDays(vector<int>& weights, int days) {
int l = 0, r = 0;
for (int w : weights) {
l = max(l, w);
r += w;
}
while (l < r) {
int mid = l + r >> 1;
if (split(weights, mid) <= days) r = mid;
else l = mid + 1;
}
return l;
}
};
制作m束花所需要的天数
（二分）
求的是摘m束花最少需要等待几天。
可以知道如果在
m * k <= bloomDay
的情况下，只要等待所有的花开就一定可以摘m束花。所以等待的天数就可以确定下来，一定在
[0, max(bloomDay[i])]
中间。
所以只要在这个范围内，计算出一个数可以使得连续的k朵花成为一束，然后得到m束花即可。并且这个数要求是一个可以满足得到花束
>=m
的一个数。这就可以使用二分了。
class Solution {
public:
int calcFlowers(vector<int>& bloomDay, int maxDays, int k) {
int cnt = 0;// 花束的个数
int flowers = 0;// 当前花的朵数
for (int day : bloomDay) {
if (day <= maxDays) {
flowers ++;
} else {
flowers = 0;
}
if (flowers == k) {
cnt ++;
flowers = 0;
}
}
return cnt;
}
int minDays(vector<int>& bloomDay, int m, int k) {
if (m * k > bloomDay.size()) return -1;
int l = 1e9, r = 0;// 已经过的天数
for (int d : bloomDay) {
l = min(l, d);
r = max(r, d);
}
while (l < r) {
int mid = l + (r - l) / 2;
if (calcFlowers(bloomDay, mid, k) >= m) r = mid;
else l = mid + 1;
}
return l;
}
};
小张的刷题计划
（二分 + 贪心）
class Solution {
public:
int CalcDays(vector<int>& time, int mid) {
int cnt = 1;
int curSum = 0;// 当前刷题累计的耗时
int maxVal = 0;// 记录耗时最多的题目
for (int t : time) {
curSum += t;
maxVal = max(maxVal, t);
if (curSum - maxVal > mid) {
cnt ++;
maxVal = t;
curSum = t;
}
}
return cnt;
}
int minTime(vector<int>& time, int m) {
int l = 0, r = 0;
for (int t : time) {
r += t;
}
while (l < r) {
int mid = l + r >> 1;
if (CalcDays(time, mid) <= m) r = mid;
else l = mid + 1;
}
return l;
}
};
总结：最大值最小化
适合的题目：1.连续的子数组的和 2.数组是非负整数