基础-二分算法 -（二分答案 | 最小化最大值 | 最大化最小值 | 第K小）-持续更新中
引入：二分的思想
二分的思想在学习语言基础和数据结构的时候多少都有接触，但是实际实现起来就会发现很多的问题，最重要的问题就是边界的判断和左右开间的问题，不过这些总的来说还是有套路的。
二分？启动！
二分查找
34.在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
本题是引入二分思想的一道经典题目，在这一题主要先了解二分的实现方法。
主要先看上面二分函数的写法。
闭区间写法
class Solution { int lower_bound(vector<int>& nums, int target) { int left = 0, right = (int) nums.size() - 1; //由于数组起始为0,right = length - 1,所以nums闭区间 [left, right] //左边界 < 右边界说明此时的二分区间还有未分到底的部分即未将范围缩小到目标数据 // = 的情况属于特殊一点的情况 //由于闭区间的写法当左右边界位置相同时还要进行修改边界值否则进入死循环 while (left <= right) { //由于闭区间的条件所以 //nums[left - 1] < target,即左边界左边都比target小 //nums[right + 1] > target,即右边界右边都比target大 //为了防止产生加法溢出的情况 int mid = left + (right - left) / 2; //当前数据大于目标值说明我们的数据太小，更靠左，所以减小右边的边界 if (nums[mid] >= target) { //由于是闭区间所以不把 right 更新为 mid right = mid - 1; // 范围缩小到 [left, mid-1] } else { //由于是闭区间所以不把 left 更新为 mid left = mid + 1; // 范围缩小到 [mid+1, right] } } //由于循环的条件所以结束后得到的left = right + 1 //这时nums[left - 1] < target //nums[left] = nums[right + 1] >= target,所以left就是第一个等于target的下标值 return left; } public: vector<int> searchRange(vector<int>& nums, int target) { int start = lower_bound(nums, target); if (start == nums.size() || nums[start] != target) { return {-1, -1}; // nums 中没有 target } int end = lower_bound(nums, target + 1) - 1; return {start, end}; } };左闭右开区间写法
class Solution { int lower_bound(vector<int>& nums, int target) { int left = 0, right = nums.size(); // 左闭右开区间 [left, right) while (left < right) { //区间为左闭右开所以循环条件中不用写 = 时的情况 int mid = left + (right - left) / 2; if (nums[mid] >= target) { //范围缩小到 [left, mid) right = mid; } else { //范围缩小到 [mid+1, right) left = mid + 1; } } //因为右边是开区间所以推出循环时 left = right //此时nums[left] = nums[right] >= target //所以 left 就是第一个 >= target 的元素下标 return left; } public: vector<int> searchRange(vector<int>& nums, int target) { int start = lower_bound(nums, target); if (start == nums.size() || nums[start] != target) { return {-1, -1}; // nums 中没有 target } // 如果 start 存在，那么 end 必定存在 int end = lower_bound(nums, target + 1) - 1; return {start, end}; } };开区间写法
class Solution { int lower_bound(vector<int>& nums, int target) { //left如果为0那么就成闭区间了，所以将left设为-1就成了开区间 int left = -1, right = nums.size(); //因为 left 为 -1 所以循环的判断条件就需要变成 left + 1 while (left + 1 < right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) { //范围缩小到 (left, mid) right = mid; } else { //范围缩小到 (mid, right) left = mid; } } //现在循环结束后 left + 1 = right //此时 nums[left] < target 而 nums[right] >= target //所以 right 就是第一个 >= target 的元素下标 return right; } public: vector<int> searchRange(vector<int>& nums, int target) { int start = lower_bound(nums, target); if (start == nums.size() || nums[start] != target) { return {-1, -1}; // nums 中没有 target } // 如果 start 存在，那么 end 必定存在 int end = lower_bound(nums, target + 1) - 1; return {start, end}; } };我们实现的lower_bound的功能类似STL中的lower_bound，查找有序序列中，第一个满足>= value的元素位置，唯一的区别就是我们实现的返回值是 int 类型而STL中返回的是迭代器。
所以下面的写法都是一样的找出另一个相同的数的位置我们找比目标值大 1 的数得到了比目标值大 1 的第一个数那么将位置减 1 就找到了最末尾的 target 值。
接下来看看库函数的写法
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int start = ranges::lower_bound(nums, target) - nums.begin(); if (start == nums.size() || nums[start] != target) { return {-1, -1}; } int end = ranges::upper_bound(nums, target) - nums.begin() - 1; return {start, end}; } };因为用库函数返回的是迭代器所以我们如果要获得下标值的话就要像指针那样减去开头位置。
经过本题的思考下一题是一道可以检验你是否理解本题的内容的，试着做一下吧。
35.搜索插入位置
35. 搜索插入位置 - 力扣（LeetCode）
本题只需要挑选一个你喜欢的二分的写法直接用，或者用库函数的写法。
704.二分查找
704. 二分查找 - 力扣（LeetCode）
这一题也很简单，还是复现上面的代码然后直接用最后对下标值进行一个条件判断，这一题建议也自己写。
public: int search(vector<int> &nums, int target) { int i = lower_bound(nums, target); return i < nums.size() && nums[i] == target ? i : -1; } };744.寻找比目标字母大的最小字母
744. 寻找比目标字母大的最小字母 - 力扣（LeetCode）
本题与之前的题目有点不太一样，之前的都是找比边界小的第一个值，而本题则是找比边界大的第一个值所以我们用的就不是 lower_bound 了，我们仍然可以手写 upper_bound 或者直接用库函数。
class Solution { public: char nextGreatestLetter(vector<char>& letters, char target) { auto it = ranges::upper_bound(letters,target); return it < letters.end() ? *it : letters[0]; } };唯一注意的还是上面说过的引用的库函数的返回类型不一样导致的迭代器的问题。
2529.正整数和负整数的最大计数
2529. 正整数和负整数的最大计数 - 力扣（LeetCode）
从这一题开始就不只是简单的用库函数再判断了，需要对题目的要求进一步思考，不过本质还是用二分的思想解决。
这一题第一眼看起来的解法就是进行遍历并统计正数和负数的数量最后再返回最大值，但是二分也可以，有人可能会问。“二分不是一半一半分割容器中数据然后查找一个目标值吗？这怎么用？”
只能说这样想看问题还是太片面了，本题中正负数是有 “分割线” 的那就是 “0”，所以我们可以找0的位置然后再统计前后两个部分的数据的数量这样就能省下部分的时间。
class Solution { public: int maximumCount(vector<int>& nums) { int pos = nums.end() - ranges::upper_bound(nums,0); int neg = ranges::lower_bound(nums,0) - nums.begin(); return max(pos,neg); } };总的来说我们一开始认为的暴力遍历实际上是一种查找，而二分也是一种查找，在有边界线的时候二分的效率是更高的。
1385.两个数组间的距离值
1385. 两个数组间的距离值 - 力扣（LeetCode）
本题的判定条件是|arr1[i]-arr2[j]| <= d如果直接用这个条件写肯定很麻烦，所以我们需要先转换一下变成对其中一个数组的判定就会简单很多。
直接设arr1[ i ]为x所以去掉绝对值再移项就成了x - d <= arr2[ j ] <= x + d，也就是判定arr2中是否有存在于[x - d,x + d]的元素，若没有就将答案加 1。
那要结合二分的思想又该如何设计？我们以上一题的思考来说，二分也是一种边界问题，同时为了判定arr2[ j ]中的元素是否有存在于[x - d,x + d]区间的。也就是说arr2中的最大值小于x - d或者arr2中的最小值大于x + d，所以我们可以根据此边界来通过二分的方法判定。
同时使用二分的前提是目标数组是排好顺序的，所以我们先将 arr2 进行排序之后用二分判定就可以了。
class Solution { public: int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) { ranges::sort(arr2); int ans = 0; for(int x : arr1) { //查找 arr2 中是否存在 >= x - d 的最小的数 auto it = ranges::lower_bound(arr2,x-d); //如果存在的数在 arr2 的末尾(指向已经不在 arr2 中了也就是不存在) //或者当前的为了寻找最小的大于 x - d 的值都大于 x //(也就是说想找的最小值都已经大于区间的最大值了) if(it == arr2.end() || *it>x+d) ans++; } return ans; } };1170.比较字符串最小字母出现频次
1170. 比较字符串最小字母出现频次 - 力扣（LeetCode）
本题由题意得出的直接想法就是分别用 f() 函数统计 queries 和 words 中最小字母的个数然后进行比较，题目中说“对于每次查询queries[i]，需统计words中满足f(queries[i])<f(W)的 词的数目”。
也就是说在查询 queries 的过程中我们比较 words 中的最小字母的个数，那么不妨先往这个思路靠过去（因为如果同时进行 queries 和 words 的查询操作再进行比较是比较麻烦的吗，而这样只单独查询 queries 是比较方便的，所以先往这个方向去想）。
怎么才能只查询 queries 的时候就比较 words 呢？那就是先用 f() 函数将 words 中的数据给处理好了，将 words 中的每个字符串中的最小字母个数存放在一个数组中。然后再遍历 queries ，遍历的过程中比较 words 中的数据。
怎么比较又是个问题，题目中我们比较的都是通过 f() 函数得来的字母个数，也就是说最后的比较操作是 queries 中得到的一个数小于哪些已经处理好的 words 数组中的数，也就是一种边界。
class Solution { public://根据题意直接实现二分的代码 int lower_bound(vector<int>& nums, int target) { //二分 int left = -1; int right = nums.size(); while (left+1 < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid; } else { right = mid; } } return right; } vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) { auto f = [](string s) { //模拟题目要求用lambda实现 f() 函数 int cnt[26] = {0}; for (char c : s) cnt[c - 'a']++; for (int x : cnt) { if (x) return x; } return 0; }; vector<int> nums; for(string c : words) nums.push_back(f(c)); //遍历words用f()函数返回每个字符串中最小的字母的个数 sort(nums.begin(),nums.end()); vector<int> ans; for(string s : queries) { //先通过 f() 函数统计在 queries 中的字符串中的最小的字母的个数 //然后在 nums 中查找最小的大于 queries 中的最小的字母的个数的下标 //通过nums的大小减去当前的下标值就剩下了后面比当前值大的数量了 //由于我们编写的 lower_bound 的返回值是下标所以在 f() 函数后还需要加 1 int n = nums.size() - lower_bound(nums,f(s)+1); ans.push_back(n); } return ans; } };2300.咒语和药水的成功对数
2300. 咒语和药水的成功对数 - 力扣（LeetCode）
由本题的题意返回值是 spells 中的每个数值分别与 potions 中的每个数值分别相乘得到的结果再进行与 success 进行判断。
假如是用循环的方法一个一个算，那么 potions 中的数将被遍历多次，所以为了减少 potions 被遍历的次数可以转变为对 spells 进行一定的操作之后再进行对 potions 的操作。
返回的是统计spells[ i ] * potions[ j ] >= success 的数量，既然直接遍历不方便，根据正难则反变成对 spells 或者 potions 其中一个的二分检测。也就是检测 potions[ j ] >= success / spells[ i ]，这样就完成了上面所说的先操作 spells 再操作 potions。
另外由于我们本章是二分的思想，那么现在再对 potions 设置二分就可以解决该题了。
class Solution { public: vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) { ranges::sort(potions); //由于spells中的每个数据仅用一次所以可以进行原地修改 for(int& x : spells)//这种写法是一种简便的写即“语法糖” x = potions.end() - ranges::lower_bound(potions,1.0*success/x); return spells; } };语法糖解释：在本题中该语法糖的展开形式如下，简单的说就是设定 x 指向spells 的第一个数据，在每一次的遍历中 x 仅为该次遍历到的数据。
auto it = spells.begin(); auto end = spells.end(); for(; it != end; ++it) { int& x = *it; //loop code... }2389.和有限的最长子序列
2389. 和有限的最长子序列 - 力扣（LeetCode）
本题要求 nums 的元素和小于某个数的最大长度，那么也就是说在 nums 中尽可能的构成的元素和的数越多，也就是尽可能将较小的数加进元素和之中越满足题意。也就是贪心的思想，那么我们在进行计算元素和之前就需要先将 nums 进行排序，这样越靠前的数就越小，方便进行元素和的求值。
将 nums 排序后元素和其实就变成了 nums 的前缀和，那么将前缀和分段计算并放入一个数组里面，越长的元素和就越靠后，并且位置也是一一对应的。同时遍历前缀和数组也方便我们比对查找满足小于 queries 的元素。
class Solution { public: vector<int> answerQueries(vector<int>& nums, vector<int>& queries) { ranges::sort(nums); partial_sum(nums.begin(),nums.end(),nums.begin());//原地计算前缀和 for(int& x : queries) x = ranges::upper_bound(nums,x) - nums.begin(); return queries; } };通过 partial_sum 可以原地计算 nums 的前缀和，因为通过前缀和就可以得出结果，而前缀和的后一个元素，又是通过前面的前缀和加上当前元素计算得来，所以可以将 nums 原地计算得到前缀和数组。
然后遍历 queries 找第一个比 queries 中该数大的前缀和的位置再减去 nums 的起始位置就可以得到长度。
当然本题可能会有一些例子上产生的小问题。
Q：示例一中的4、5、1怎么解释？
A：我认为示例给的太恰巧了，因为本题本来就是越长越合法，而为了满足越长肯定是将数组中较小的数都加起来是更好的解法。就拿示例1来说排序后的 1、2、4也是满足条件的，如果说去掉一个 2 来换 5 的话，那么如果前面还有别的比 5 小的数的话那肯定就不满足题意了。