二分特训上------理论部分----Week4(附带LeetCode特训)_小杰312的博客-CSDN博客
如果需要理论，请移步上一篇.
/*****
注意：我们把
0000001111111模型中：0称呼为左边区间，1称呼为右边区间 (答案第一个1在右区间)
1111100000000模型中：1称呼为左区间，0称呼为右区间 （答案最后一个1在左区间）
二分查找就是不断收缩区间，并且保证最终结果一定在留下的区间中。（真的猛，理解它）另外二分边界问题。有单独处理它的办法。比如大区间二分查找，小区间线性查找。
查找的本质就是排除不要的，留下要的，并找到要的。
几乎还是上面的那几句话：保证正确答案在区间中的同时按照mid和target的大小关系判断target和mid的位置关系。进而根据位置关系收缩区间。不断的收缩target的生存区间，直至答案。
********/
二分搜索变形，就是搜索00000011111中出现的第一个1，以及11111000中最后出现的一个1.
35. 搜索插入位置
https://leetcode.cn/problems/search-insert-position/
思路：首先数组已经是一个排序好的数组，所以满足随数组下标的单调递增，数组值单调性变化的前提。arr[ind] 相当于是 func(ind)。找这个值，但是注意：这个值可能不存在于该数组之中。那么我们就需要将其插入到第一个比他大的元素的前面去。 就比如说吧：123 56. target是4. 那么插入进来就应该是 123456。4插入到了第一个>4的5位置上面去了。 题意等价《=》寻找第一个nums[ind] >= target 的 位置。
思路伪代码化：
/*****
注意：我们把0000001111111模型中：0称呼为左边区间，1称呼为右边区间 (答案第一个1在右区间)
1111100000000模型中：1称呼为左区间，0称呼为右区间 （答案最后一个1在左区间）
二分查找就是不断收缩区间，并且保证最终结果一定在留下的区间中。
********/
int binarySearch(单调映射条件数组arr, 目标值target) {
l, r, mid; //左边界指针, 右边界指针, 中间值. 留下的区间【l, r】
while (r - l > 3) {//只要搜索区间的大小 > 4就进行二分
mid = (l+r)/2; //获取中间位置作为基准.进行缩小答案区间
if (arr[mid] < target) l = mid + 1;//mid处在左区间, 但是答案在右区间第一个1
else r = mid;//why r != mid - 1? mid可能是答案。
}
for (; l <= r; l ++)
if (arr[l] >= target) return l;//找到第一个1return
return -1;
}code:
class Solution {
//插入的位置, 如果这个元素不存在，就应该插入到第一个>= 该值的位置
int binarySearch01_(vector<int>& nums, int target) {
int l = 0, r = nums.size()-1, mid;
while (r - l > 3) {
mid = l + ((r-l) >> 1);
if (nums[mid] < target) l = mid + 1;
else r = mid;
}
for (; l <= r; l ++ ) {
if (nums[l] >= target) return l;
}
return nums.size();//没有一个大于他的。只能查到末尾了
}
public:
int searchInsert(vector<int>& nums, int target) {
return binarySearch01_(nums, target);
}
};34. 在排序数组中查找元素的第一个和最后一个位置
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
话不多说：本质，找寻本质。什么是本质？第一个出现的位置，不就是左区间嘛，最后一个出现的位置不就是右区间嘛。这部妥妥的，最后一个1，和第一个1嘛。11111111000000模型的最后一个1，经典的查找最后一个位置的。000000000011111111，经典的查找第一个1的。第一个出现的位置的。 （加深理解。这个1：就是符合题干要求，0，就是不符合题干要求。）
上面那道题写的足够清楚，这个直接给出code:
class Solution {
//查找右区间. 最后一个出现的 <= target的 1
int binarySearch10_(std::vector<int>& nums, int target) {
int l = 0, r = nums.size()-1, mid;
while (r - l > 3) {
mid = l + ((r-l) >> 1);
if (nums[mid] > target) r = mid - 1;
else l = mid;
}
for (; r >= l; r --) {
if (nums[r] == target) return r;
}
return -1;//找不到
}
//查找左区间, 第一个出现的满足 >= target 条件的1
int binarySearch01_(std::vector<int>& nums, int target) {
int l = 0, r = nums.size()-1, mid;
while (r - l > 3) {
mid = l + ((r-l) >> 1);
if (nums[mid] < target) l = mid + 1;
else r = mid;
}
for (; l <= r; l ++) {
if (nums[l] == target) return l;
}
return -1;//找不到
}
public:
vector<int> searchRange(vector<int>& nums, int target) {
int ind1 = binarySearch01_(nums, target);
int ind2 = binarySearch10_(nums, target);
return {ind1, ind2};
}
};33. 搜索旋转排序数组
https://leetcode.cn/problems/search-in-rotated-sorted-array/
题解：旋转排序数组？何意。旋转，也就是说将前面的一段有序序列换到数组末尾去了，把数组末尾的一段有序序列换到前面去了。至此。数组前后段各自顺序。但是整体前面的一段大于后面的一段罢了。 此题还没有重复。 ------ 抓本质：本题整体来看还是单调增加的。那么我们自然还是可以使用二分查找来处理。不过，我们需要从二分查找的本质入手，前面说过二分查找的本质就是不断的压缩正确结果所在的区间，将非正确结果的元素从区间中剔除.
从整体来看。如下就是朴素二分的核心。我们先抛开此题旋转不谈，整体的二分指针的偏移，区间的压缩方式应该按照如下方式。
if (mid就是正确结果target) return mid;
if (正确结果target在mid的右边) l = mid + 1;
else r = mid -1; //即为正确结果target在mid左边
其次：我们需要考虑 mid 所在区间，以及target所在区间。因为这两者的区间不同，决定了上面的写法。 比如说：mid 在左边区间, target在右边区间.则target肯定在mid的右边，或者mid和target同区间，但是target > nums[mid] 则也说明target在mid右边。 懂否？？？ 因为旋转性带来的数组可能不是纯粹的单调。所以我们需要划分左右局部单调区间。mid和target在同一区间和不在同一区间的处理方式是不一致的。
Code再体味。
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size()-1, mid;
while (l <= r) {
mid = l + ((r-l) >> 1);
//先判断所处区
if (nums[mid] == target) return mid;
if (nums[mid] > nums[r]) { //mid处在左区间
if (target <= nums[r] || target > nums[mid]) l = mid + 1;
// ans 在 mid 右边所有情况
else r = mid - 1;
} else {//mid处在右区间
if (target > nums[r] || target < nums[mid]) r = mid - 1;
//考虑 ans 在 mid 左边所有情况
else l = mid + 1;
}
}
return -1;//找不到咯.
}
};81. 搜索旋转排序数组 II
https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/description/
上一题便已经道出了此题真正的核心了。就是抓住target跟mid的位置关系进行压缩target的生存空间，最终卡出最终的target。不过上一题没有重复，判断区间很容易。此题存在重复。一旦存在重复。则左右区间的判定难度骤然增长。（因为可能有这种情况 4444567123444）左右区间都含有这个最小的边界元素。这该如何是好？ 貌似依靠mid和左边界或者右边界的大小关系来判定都不好使了呀。
做个预处理：走掉一边区间的所有重复起点元素。避免其对于左右区间位置判定的一个影响。就比如说上面的那个4444567123444 处理完成之后就是 567123444了。这样只要mid > nums[最右下标] mid就一定在左区间。否则在右区间。否则针对===的情况根本无法判断处在何区间
class Solution {
public:
bool search(vector<int>& nums, int target) {
int l = 0, n = nums.size() , r = n-1, mid;
int rNum = nums[n-1];
//预处理，走掉多余的左区间起点元素。防止其对于mid所处区间的判断干扰
while (l < r && nums[l] == rNum) l ++;
while (l <= r) {
mid = l + ((r-l) >> 1);
if (nums[mid] == target) return true;
if (nums[mid] > nums[n-1]) {//mid 处在左区间
if (target <= rNum || target > nums[mid]) l = mid + 1;//target在mid右边
else r = mid - 1;
} else { //mid 处在右区间
if (target > rNum || target < nums[mid]) r = mid - 1;//target在mid左边
else l = mid + 1;
}
}
return false;
}
};153. 寻找旋转排序数组中的最小值
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/
核心思路：几乎还是上面的那几句话：保证正确答案在区间中的同时按照mid和target的大小关系判断target和mid的位置关系。进而根据位置关系收缩区间。不断的收缩target的生存区间，直至答案。 ---- 最小值在右边区间。并且 4561234 nums[mid] < nums[mid-1] .
class Solution {
public:
//核心，保证答案还在二分区间中.
int findMin(vector<int>& nums) {
int n = nums.size();
if (nums[0] < nums[n-1]) return nums[0];//相当于没有旋转
int l = 0, r = n-1, mid;
while (l < r) {
mid = l + ((r-l) >> 1);
if (nums[mid] > nums[n-1]) {//左区间. 不可能是答案
l = mid + 1;
} else {//右区间 OR ans.
if (nums[mid] < nums[mid - 1]) {//最好加上mid-1存在的判定
return nums[mid];//ans
} else {
r = mid - 1;
}
}
}
return nums[l];
}
};278. 第一个错误的版本
https://leetcode.cn/problems/first-bad-version/description/
核心思路：右边第一个1没啥核心的。 标准0000001111模型。找第一个1.
class Solution {
public:
int firstBadVersion(int n) {
int l = 1, r = n, mid;
while ( r - l > 3) {
mid = l + ((r-l) >> 1);
if (!isBadVersion(mid)) l = mid + 1;
else r = mid;
}
for (; l <= r; ++l ) {
if (isBadVersion(l)) return l;
}
return -1;
}
};前缀和，后缀和天然的随着下标的增加。前缀数目增加，前缀和单调增加。所以具备单调性。我们可以采用二分查找提高查找效率。
1658. 将 x 减到 0 的最小操作数
https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/
题解：说白了。这种题目就纯纯粹粹的积累。刚拿到，第一次其实多半是判断不出来可以二分查找的。虽然因为只能不停的从数组开头和结尾进行打掉元素可以大致判断出和前后缀和似乎有点关联。因为数组最左边就属于前缀嘛，数组末尾就属于后缀嘛。这一点不难推导。
至于 这 前缀和后缀元素和 == x 才能恰好打掉x. 所以问题可以转换<=> presum[i] + suffsum[j] == x 也就是前i个元素和末尾j个元素打掉，凑出来x.
到了此处，可能还有兄弟说，欸欸欸，这不是那个啥嘛。啥啥啥？对头两数和问题。还是很经典的，也可以用二分。当然。二分一次只能查找一个数字，所以我们的查找方式需要转变成定一议论二。 suffSum[i] = x - preSum[j]嘛。 我们可以遍历所有i(前缀)的同时搜索是否存在符合的后缀。注意前后缀不重合。这也算是一个坑。自然补充和。那么就从i + 1开始寻找可能的后缀。当然由于后缀数组是和前缀数组逆向。所以也就是从后缀的n-1作为右区间。开始查找。
Coding:
class Solution {
int binarySearch(std::vector<int>& nums, int r, int target) {
int l = 0, mid;
while (l <= r) {
mid = l + ((r-l) >> 1);
if (nums[mid] == target) return mid;
if (nums[mid] > target) r = mid - 1;
else l = mid + 1;
}
return -1;
}
public:
int minOperations(vector<int>& nums, int x) {
int n = nums.size();
std::vector<int> preSum(n+1);
std::vector<int> suffSum(n+1);
for (int i = 0; i < n; ++i) {
preSum[i+1] = preSum[i] + nums[i];
suffSum[i+1] = suffSum[i] + nums[n-i-1];
}
//preSum[i] 相当于前i个元素和. suffSum[j] 后 j个元素和
int ans = INT_MAX;
for (int i = 0; i <= n; ++i) {
if (preSum[i] > x) break;//没必要找下去了.
int j = binarySearch(suffSum, n-i, x-preSum[i]);
if (j != -1) ans = min(i+j, ans);
}
return ans != INT_MAX ? ans : -1;
}
};209. 长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/description/
解题思路：大差不差吧。这个题目和上一题。子数组。也就是区间和 preSum[j] - preSum[i] >= target. 因为是长度最小。所以还可以读出来第一个1的深意在其中。i 定下来。j增加，preSum[i]不断增加，迟早区间和 >= target，但是题目要求长度最小，soso, 需要找出来的j下标尽可能小。也就是在二分查找中的第一个出现。因为只有第一个出现才能保障ind尽可能小。自然也就是0000111模型的第一个1
class Solution {
//二分搜索之定一议2 >= 最小长度 00000000111 第一个1, 第一个>=
int binarySearch(std::vector<int>& nums, int l, int target) {
int r = nums.size()-1, mid;
while (r - l > 3) {
mid = l + ((r-l) >> 1);
if (nums[mid] < target) l = mid + 1;
else r = mid;
}
for (; l <= r; l ++ ) {
if (nums[l] >= target) return l;
}
return -1;
}
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
std::vector<int> preSum(n+1);
for (int i = 0; i < n; ++i) preSum[i+1] = preSum[i] + nums[i];
//相当于是 preSum[j] - preSum[i] >= target. 则 preSum[j] >= preSum[i] + target.
//定一议二的方式.
int ans = INT_MAX;
for (int i = 0; i <= n; ++i) {
int j = binarySearch(preSum, i, target+preSum[i]);
if (j != -1 ) ans = min(ans, j - i);
}
return ans == INT_MAX ? 0 : ans;
}
};69. x的平方根
https://leetcode.cn/problems/sqrtx/
题解思路：思路还是很简单的，我们将f当作是arr[x] f(x) 相当于是 x^(0.5). 核心。随着x的增加，x的算数平方根具有像x一样的单调性。故而可以二分搜索。这个不难，直接看代码能理解。
用x/mid和mid以及mid+1关系来判断答案所处区间，而没有直接采取mid*mid和x的大小关系进行判断。是因为可能超出int范围。
class Solution {
public:
int mySqrt(int x) {
if (x == 0 || x == 1) return x;
int l = 0, r = x, mid;
while (l <= r) {
mid = l + ((r - l) >> 1);
if (mid <= x/mid && mid+1 > x/(mid+1)) return mid;
if (mid < x/mid) l = mid + 1;
else r = mid - 1;
}
return mid;
}
};1011. 在 D 天内送达包裹的能力
https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/
class Solution {
int f(std::vector<int>& weights, int capacity) {
int day = 1, ind = 0, cap = capacity;
while (ind < weights.size()) {
cap -= weights[ind], ind ++;
if (ind == weights.size()) break;
if (cap < weights[ind]) {//说明今天拉满货物了。
cap = capacity;
day += 1;
}
}
return day;
}
public:
int shipWithinDays(vector<int>& weights, int days) {
int r = accumulate(weights.begin(), weights.end(), 0);
int l = 0, mid;
for (auto w : weights) {
l = max(l, w);
}
while (r - l > 3) {// 左边运输时间长 00001
mid = l + ((r-l) >> 1) ;
if (f(weights, mid) > days) l = mid + 1;
else r = mid;
}
for (; l <= r; l ++) {
if (f(weights, l) <= days) return l;
}
return -1;
}
};思路点播：随着运载能力的提升。每天可以运载的货物的量cap的提升。运货所需要的天数递减。所以具备单调性。可以进行二分搜索。二分搜索注意：答案一定在保留区间中，以及正确的考虑单调性和f(mid)以及days的大小关系，来判断好mid所处区间，答案所处区间，答案如果在mid左边，自然就是r = mid-1 答案在mid右边 自然就是l = mid + 1. 如果mid可能就是答案，则不可以+1或者-1以免跳过答案。
475. 供暖器
https://leetcode.cn/problems/heaters/
/**
* @ 供暖器固定, 加热半径越大. 可以供暖的房子越多
* @ 加热半径 和 供暖房子呈现单调关系.
* @ 现在需要 恰好可以供暖周围所有的房子.
* @ 真正的ans 加热半径铁定在minLen 和 maxLen之间
* @ 可以照亮 >= houses. 00001111 第一个1
* @ 此题想到二分很简单，但是最难搞的是二分条件的判定, 如何判定是否可以覆盖所有房间
*/
class Solution {
bool check(vector<int>& houses, vector<int>& heaters, int r) {
int i = 0, j = 0;
//核心关键，必须每一个房间全部辐射上
while (i < houses.size() && j < heaters.size()) {
if (abs(heaters[j]-houses[i]) <= r) i ++;//可以辐射上i房间
else j ++;//不能辐射上i房间了。换下一台炉子
}
return i == houses.size();//走出去了. 辐射到所有房间了
}
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
std::sort(houses.begin(), houses.end());
std::sort(heaters.begin(), heaters.end());
int maxLen = 1000000000;
int l = 0, r = maxLen, mid;
//搜索最小的min加热半径
while (l < r) {
mid = l + ((r-l) >> 1);
if (!check(houses, heaters, mid)) l = mid + 1;
else r = mid;
}
return l;
}
};410. 分割数组的最大值
https://leetcode.cn/problems/split-array-largest-sum/description/
本质：和运输能力那道题目一毛一样。
/*
题目分析：
分割子数组的和的最值相当于是一个限制。
一个cap限制，此处跟装货运输有点像。
每次最多装货就是cap, 也就是max(子数组之和)
求 cap 最小.
很明显 cap 单调增加，m 就单调减少
cap 单调减小, m 就 单调增加
m 随着 cap 的单调增加而减少。(f(cap) == m)
000000000111111111的第一个1
*/
class Solution {
int f(std::vector<int>& nums, int _cap) {
int cap = _cap, cnt = 1, ind = 0;
while (ind < nums.size()) {
cap -= nums[ind], ind ++;
if (ind == nums.size()) break;//结束了.
if (cap < nums[ind]) {//没结束，但是上一轮已经装完了
cnt ++;
cap = _cap;//重新装载，新的一轮，新的一个子数组区间了
}
}
return cnt;
}
public:
int splitArray(vector<int>& nums, int k) {
int l = 0, r = accumulate(nums.begin(), nums.end(), 0), mid;
for (int num : nums) l = max(l, num);
while (r - l > 3) {
mid = l + ((r-l) >> 1);
if (f(nums, mid) > k) l = mid + 1;
else r = mid;
}
for (; l <= r; l ++) {
//少一个区间也可以成为答案. 不装那么多就好了
if (f(nums, l) <= k) return l;
}
return -1;
}
};
一道引人深思的二分答案题目. 甚至可以说这样的题目才算是比较纯粹的二分答案题目。纯粹的二分答案题目，本来就是用精度作为二分查找的退出条件。但是我们上述讨论的题目，明显精度都只是1.以整数作为精度。 一般OJ都是这种题目，会限制精度。
//切绳子：
/*
三段绳子：
___ ___ ___ ___ 4米长绳子
___ ___ ___ ___ ___ ___ 6米绳子
___ ___ ___ 三米绳子
需要切除k=4根绳子 问？绳子的最大长度。绳子不可拼接.
很明显ans = 3米.
需要切除k根绳子. 明显, 如果
*/
//切绳子：
/*
三段绳子：
___ ___ ___ ___ 4米长绳子
___ ___ ___ ___ ___ ___ 6米绳子
___ ___ ___ 三米绳子
需要切除k=4根绳子 问？绳子的最大长度。绳子不可拼接.
很明显ans = 3米.
需要切除k根绳子. 明显, 如果
*/
//范围, 误差范围, 精度控制。
#define EPS 1e-2
int f(std::vector<double> nums, double needLen) {
int ans = 0;
for (auto& len : nums) ans += (int)len/needLen;
return ans;
}
double maxLen(vector<double>& nums) {
double ans = 0;
for (auto& e : nums) {
ans = max(e, ans);
}
return ans;
}
//需要绳子最长，尽量最长, 再长也该有个范围限制吧. 缩小范围到一定程度.
double binarySearchAns(std::vector<double>& nums, int k) {
double l = 1, r = maxLen(nums), mid;
while (r - l > EPS) {//l <= r
mid = l+(r-l)/2; //中间.
if (f(nums, mid) < k) r = mid;//不能是mid + 1, 因为精度不是整数.
else l = mid;
}
return r;
}
//f(num) a[num]
int main() {
std::vector<double> nums{4.0, 6.0, 3.0};
int k = 4;
std::cout << binarySearchAns(nums, k) << std::endl;
}