目录
前言
二分答案与二分查找【算法深练】二分查找：从O(n)到O(log n)以对数级效率秒杀海量数据的解题利刃-CSDN博客有异曲同工之妙，与二分查找不同的是：二分答案需要自己编写check函数来判断是否成立。二分答案在我们解题中是比较常用的，如果一个题目无从下手，可以先思考如果在已知答案的情况下，对答案进行判断是否更简单，如果更简单就可以考虑使用二分来AC。
PS：本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单。
二分求最小值
1283. 使结果不超过阈值的最小除数
题解：找到一个不大于threshold的整数，找到数组中除以该整数后仍然小于thorshold的最小除数。根据nums.length<=threshold如果除数是最大值结果就是nums.length满足条件，所以区间就在(0,max(nums)]中对该区间中的所有数进行枚举找到满足条件的最小值，时间复杂度是O(N^2)太慢了。当除数变大的时候结果就在减小，那不就是单调的吗，能使用二分来解决；将左右边界分别设置为0和max(nums)，进行二分找到满足条件的最小值。细节：向上取整a/b就是(a+b-1)/b向下取整。
class Solution {
//计算如果除数是x结果时多少
int div(vector<int>& nums,int x)
{
int ret=0;
for(auto e:nums) ret+=(e+x-1)/x;
return ret;
}
public:
int smallestDivisor(vector<int>& nums, int threshold) {
int n=nums.size();
//以数组小标表示除数，随着下标增大结果也在减小所以可以使用二分
int left=0,right=ranges::max(nums); //使用左开右开的形式 n<=threshold所以最大值是除数为nums[n-1]时结果是n
while(left+1<right)
{
int mid=left+(right-left)/2;
if(div(nums,mid)<=threshold) right=mid; //满足条件
else left=mid; //不满足条件
}
return right;
}
};2187. 完成旅途的最少时间
题解：与类似，当时间在增大时旅途趟数也在增加是递增的可以使用二分进行查找。左右边界怎么进行设置呢？？？右边界可以设置为min(time)*totalTrips表示最快的车独自完成的时间，左边界可以直接设置为0，也可以设置为min(time)。
class Solution {
//时间time内完成的旅途数目
long long numsTime(vector<int>& nums,long long time)
{
long long ret=0;
for(auto e:nums) ret+=time/e;
return ret;
}
public:
long long minimumTime(vector<int>& time, int totalTrips) {
//以时间作为二分，时间越长可以完成的旅途越多是单调的
//最长时间可以设置为：min(time)*totalTrips即花费最短时间的车辆独自完成时间
long long left=0,right=(long long)ranges::min(time)*totalTrips;
while(left+1<right)
{
long long mid=left+(right-left)/2;
if(numsTime(time,mid)>=totalTrips) right=mid;
else left=mid;
}
return right;
}
};1011. 在 D 天内送达包裹的能力
题解：当运输能力上升时，所需要的时间就在减小所以满足递减，可以使用二分。在下边界世界设置为0即可，上边界设置为：全部包裹是max(weight)的情况下需要的载重能力，即max(weight)*((n-1)/days+1)，其中((n-1)/days+1)表示一天至多运输货物的数量；上边界也可以使用所有货物的总重量，表示一天就装完所需的载重能力。
class Solution {
//计算运载能力为x时需要的时间
long long time(vector<int>& nums,long long x)
{
long long tmp=0,ret=0;
for(auto e:nums)
{
if(e>x) return -1;
tmp+=e;
if(tmp>=x)
{
ret++;
tmp=tmp==x?0:e;
}
}
if(tmp) ret++;
return ret;
}
public:
int shipWithinDays(vector<int>& weights, int days) {
//船运载能力越强所需的时间就越短，是单调递减的可以使用二分来解决
int n=weights.size();
//右边界设置为如果货物全是weight的最大值当时间为days时需要的运载能力
//(n-1)/days+1表示包裹数量除以天数向上取整，即一天至多需要运输多少个包裹
long long left=0,right=ranges::max(weights)*((n-1)/days+1);
while(left+1<right)
{
long long mid=left+(right-left)/2;
int need=time(weights,mid);
if(need>0&&need<=days) right=mid;
else left=mid;
}
return right;
}
};875. 爱吃香蕉的珂珂
题解：速度越快需要的时间就越小，单调递减可以使用二分查找；下边界可以使用0表示，上边界使用piles的和表示。
class Solution {
long long hours(vector<int>& nums,long long v)
{
long long ret=0;
for(auto e:nums)
ret+=(e-1)/v+1;
return ret;
}
public:
int minEatingSpeed(vector<int>& piles, int h) {
//速度越大，所需要的时间越短，单调递减的可以使用二分解决
//细节：她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。 说明需要进行向上取整
int n=piles.size();
//下边界用0来表示，上边界可以用所有的香蕉个数表示
long long left=0,right=accumulate(piles.begin(),piles.end(),0LL);
while(left+1<right)
{
long long mid=left+(right-left)/2;
if(hours(piles,mid)<=h) right=mid;
else left=mid;
}
return right;
}
};3296. 移山所需的最少秒数
题解：当花费的时间越多时高度降低的就越多，所以可以使用二分来找最小值。下边界可以使用0，上边界可以用最快的工人一个人移山所需要的时间。
计算一个工人在t时间内可以降低的高度：
class Solution {
//计算所有工人在t内降低的高度
long long totalHeight(vector<int>& nums,long long t)
{
long long ret=0;
for(auto e:nums) ret+=height(e,t);
return ret;
}
//计算工人在时间t内降低的高度
long long height(int worktime,long long t)
{
long long k=t/worktime;
long long len=(-1+sqrt(1+8*k))/2;
return len;
}
public:
long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
//当时间越多降低的高度越长，可以使用二分解决
long long left=0,right=0;
long long heig=0,mintime=ranges::min(workerTimes),each=0;
//确定上边界right
while(heig<mountainHeight)
{
each+=mintime;
right+=each;
heig++;
}
while(left+1<right)
{
long long mid=left+(right-left)/2;
if(totalHeight(workerTimes,mid)>=mountainHeight) right=mid;
else left=mid;
}
return right;
}
};475. 供暖器
题解：当半径越大时越满足条件，房屋只存在能供暖和不能供暖两种情况，所以可以使用二分进行查找；对于二分判断是否满足条件不需要考虑太多，直接将设置的x带入题目进行检验即可。
class Solution {
//检查当前x时候满足条件
bool check(vector<int>& houses,vector<int>& heaters,int x)
{
int n=houses.size(),m=heaters.size();
int j=0;
for(int i=0;i<n;i++)
{
if(houses[i]>=heaters[j]-x&&houses[i]<=heaters[j]+x) continue;
while(j<m&&houses[i]>heaters[j]+x) j++;
if(j==m||houses[i]<heaters[j]-x) return false;
}
return true;
}
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
//先对两个数组进行排序
sort(houses.begin(),houses.end());
sort(heaters.begin(),heaters.end());
int left=-1,right=1000000000; //设置上下边界
while(left+1<right)
{
int mid=left+(right-left)/2;
if(check(houses,heaters,mid)) right=mid;
else left=mid;
}
return right;
}
};2594. 修车的最少时间
题解：与上一题类似，依旧是使用二分来解决。先确定上下边界，下边界直接设为0，上边界可以使用最快修理工独自完成所需要的时间。
class Solution {
long long check(vector<int>& ranks,long long t)
{
long long ret=0; //统计修理好的车辆
for(auto r:ranks) ret+=sqrt(t/r);
return ret;
}
public:
long long repairCars(vector<int>& ranks, int cars) {
//确定上下边界
long long left=0,right=0;
long long r_min=ranges::min(ranks);
right=r_min*cars*cars;
while(left+1<right)
{
long long mid=left+(right-left)/2;
if(check(ranks,mid)>=cars) right=mid;
else left=mid;
}
return right;
}
};1482. 制作 m 束花所需的最少天数
题解：二分+分组循环；对时间进行二分，下边界使用0，上边界可以使用bloomDay中的最大值；使用check来判断时间t是否满足条件。
class Solution {
//检查在t时刻是否满足条件
bool check(vector<int>& nums,int m,int k,int t)
{
int i=0,n=nums.size();
while(i<n)
{
while(i<n&&nums[i]>t) i++;
int start=i++;
while(i-start!=k&&i<n&&nums[i]<=t) i++;
if(i<=n&&i-start==k) m--;
if(m==0) return true;
}
return false;
}
public:
int minDays(vector<int>& bloomDay, int m, int k) {
int n=bloomDay.size();
if((long long)k*m>n) return -1; //数量不够直接返回
int left=0,right=ranges::max(bloomDay); //取上下边界
while(left+1<right)
{
int mid=left+(right-left)/2;
if(check(bloomDay,m,k,mid)) right=mid;
else left=mid;
}
return right;
}
};3048. 标记所有下标的最早秒数 I
题解：此题难度较大，直接计算时间比较难，但是如果已知答案确定答案是否正确就比较简单，就是二分。标记所有的下标，时间越多越有可能进行标记，所以可以根据时间进行二分。
题意转换：此题可以理解为有n+1场考试[1,n]，我们需要对考试进行准备，每一场考试需要准备的时间是确定的，考试可以有多场；根据上面转换后的题意，如果考试越靠后就有更多的时间进行准备，那就可以只准备每门考试的最后一场即可。
代码细节：统计每门考试的最后一场时间，当时间到最后一场时必须进行考试，看前面可以准备的时间够不够即可。
class Solution {
//检查时间为t时，是否满足条件
bool check(vector<int>& nums,vector<int>& changeIndices,int t)
{
int n=nums.size();
vector<int> last_n(n,-1);
for(int i=0;i<t;i++)
last_n[changeIndices[i]-1]=i; //存储各个科目最后一次考试时间
if(ranges::find(last_n,-1)!=last_n.end()) return false; //存在没有考试时间的科目
int have=0;
//i表示时间,changeIndices[i]-1是第几门科目,nums[changeIndices[i]-1]是该门复习需要的时间
for(int i=0;i<t;i++)
{
if(i==last_n[changeIndices[i]-1])
{
if(have<nums[changeIndices[i]-1]) return false;
else have-=nums[changeIndices[i]-1];
}
else have++;
}
return true;
}
public:
int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
int n=nums.size(),m=changeIndices.size();
if(n>m) return -1;
int left=n-1,right=m+1; //不能确定时间为m时是否满足条件，但是m+1是一定不满足条件的所以将right置为m+1
while(left+1<right)
{
int mid=left+(right-left)/2;
if(check(nums,changeIndices,mid)) right=mid;
else left=mid;
}
return right>m?-1:right;
}
};求最小值拓展（浮点型）
1870. 准时到达的列车最小时速
题解：依旧是二分，但是此题需要特别注意的是小数的处理方式，以及左右边界的处理细节。细节：列车都是整点运行的，所以除了最后一辆列车其他的列车运行时间都要进行向上取整。
class Solution {
//检查是否满足条件
//因为车都是在整数时间发车的所以要进行向上取整
bool check(vector<int>& dist,double hour,int v)
{
int n=dist.size();
double total=0;
for(int i=0;i<n-1;i++)
total+=(dist[i]-1)/v+1;
total+=dist[n-1]/(double)v;
return total<=hour;
}
public:
int minSpeedOnTime(vector<int>& dist, double hour) {
//当速度越大时多需要的时间也短，可以使用二分的方式来求最小速率
int n=dist.size();
if(n-1>=hour) return -1; //车次-1时因为最后一次算的是小数而并不需要取整
long long left=0,right=ranges::max(dist); //right用dist中的最大值替代，这样每辆车都只需要行驶一个小时
double point=hour-(int)hour; //如果最后一次出现小数时就需要对最后一次车速进行判断，来确定right是否需要扩大
if(point!=0&&dist[n-1]/point>right) right=dist[n-1]/point+1;
while(left+1<right)
{
int mid=left+(right-left)/2;
if(check(dist,hour,mid)) right=mid;
else left=mid;
}
return right;
}
};3453. 分割正方形 I
题解：易得y一定是存在的，所以此题的难点在于如何确定循环条件。此题以y作为二分基准，当下方面积更大（没有找到准确位置）或者上下面积差在题目范围内（找到了满足条件的位置，但是可能不是最小y ）时将right=mid，否则将left=mid；
循环条件应该如何进行设置？？？
class Solution {
//判断以t为分界线是否满足条件
bool check(vector<vector<int>>& squares,double t)
{
double down=0,up=0;
for(auto& nums:squares)
{
double x=nums[0],y=nums[1],len=nums[2];
if(y+len>t)
up+= len*min(y+len-t,len); //注意此处不能直接将len*(y-len-t)其中间可能有空隙
if(y<t)
down+= len*min(t-y,len);
}
return up<down||abs(up-down)<=1e-5; //当下面面积大时right就需要下移，当满足条件时right也下移找最小值
}
public:
double separateSquares(vector<vector<int>>& squares) {
double left=0,right=0;
for(auto nums: squares)
if(nums[1]+nums[2]>right) right=nums[1]+nums[2];
for(int i=0;i<48;i++) //通过计算可以设置循环次数来对数据进行精确
{
double mid=left+(right-left)/2.0;
if(check(squares,mid)) right=mid;
else left=mid;
}
return right;
}
};上面通过计算直接确定了循环的次数，但是如果仍然像之前一样写也是可以的，
for(int i=0;i<48;i++)可以写成while(left+1e-5<right)，此写法仍然控制了区间长度不超过1e-5.
但是此处不建议用while本题能够过是因为left和right的值较小，当left值很大的时候left+1e-5的结果可能不再是我们预期的结果，此处与浮点数的存储有关，下面进行简单解释；
存储浮点数的时候会先将浮点数转换为(1.xxxxxxxxxx)*(10^m)的形式在64位下只有52个比特位来存储小数点后面的数据，所以浮点数实际上是不连续的，也就是说1.0的下一个浮点数是1+2^(-52)，当这个数越大的时候其下一个浮点数也就越大，所以当left很大时left+1e-5还是left，就会进入死循环。
拓展：此题如果数据范围较小的话，也可以将所有的整数都提升10^5来将浮点数二分转化为整数二分。
二分求最大值
求最大值和求最小值的方法是类似的，只不过判断条件不一样。
275. H 指数 II
题解：数组是单调递增的，当h越大的时候需要的优质论文的个数就越多；所以可以使用二分来找到满足条件的h。假设论文被引用的次数>=h的个数是i，当i>=h时说明满足条件但是不一定是最大的一个让left=mid，当i<h时说明right太大了，所以将right进行缩小right-mid即可。
class Solution {
//h表示论文被应用的次数
bool check(vector<int>& nums,int h)
{
int n=nums.size();
int pos=ranges::lower_bound(nums,h)-nums.begin();
//判断是否有h个值满足条件
return n-pos>=h;
}
public:
int hIndex(vector<int>& citations) {
//数据是有序的，可以通过二分来进行查找
int n=citations.size();
int left=0,right=citations[n-1]+1;
while(left+1<right)
{
int mid=left+(right-left)/2;
if(check(citations,mid)) left=mid;
else right=mid;
}
return left;
}
};2226. 每个小孩最多能分到多少糖果
题解：当直接求答案比较难的时候，可以考虑用验证法；在已知答案的情况下，对答案的正确性进行验证，就是二分。使用二分先确定一个分到的糖果数，再检验该答案是否正确即可。
class Solution {
//能否每人分到x个糖果
bool check(vector<int>& nums,long long x,long long k)
{
long long count=0; //记录能有多少人分到x个糖果
for(auto e:nums) count+=e/x;
return count>=k;
}
public:
int maximumCandies(vector<int>& candies, long long k) {
//直接进行求比较难，但是如果已知答案判断答案是否正确就比较简单了
//已知答案就需要考虑二分
long long left=0,right=ranges::max(candies)+1;
while(left+1<right)
{
long long mid=left+(right-left)/2;
if(check(candies,mid,k)) left=mid;
else right=mid;
}
return left;
}
};2982. 找出出现至少三次的最长特殊子字符串 II
当出现了相同子字符串时，第一时间想到的是滑动窗口。用滑动窗口求出每一个相同子串，每个相同字符串又可以进行分割出更多的子字符串，将这些字符串进行统计找出出现三次以上的最长子串。看起来好像可以！！！
class Solution {
public:
int maximumLength(string s) {
//使用一次滑动窗口
unordered_map<string ,int> m;
int n=s.size();
int i=0;
while(i<n)
{
int start=i;
while(i<n&&s[start]==s[i]) i++;
//此时相同字符串的长度为i-start
int len=i-start;
string str(s.begin()+start,s.begin()+i);
for(int k=len;k>=0;k--)
m[str.substr(0,k)]+=len-k+1; //进行统计
}
//所有相同的字符串都存储到m中了，找长度最长的并且有3个
int ret=-1;
for(auto& [str,k]:m)
{
if(k>=3) ret=max(ret,(int)str.size());
}
return ret;
}
};以上对思路进行实现，但是没有过，是的。因为当相同字符串很长时就会导致map中存储了大量字符串导致最后内存超出限制！！！。
所以需要对代码进行优化，每次统计的时候都是直接把所有的子字符串都统计进去，能不能进行一点裁剪，可以。对for循环进行修改：for(int k=len;k>=len-2&&k>0;k--)只需要统计最长的三个即可，因为如果一个相同字符串长度为len则其满足条件的长度至少为len-2。
class Solution {
public:
int maximumLength(string s) {
//使用一次滑动窗口
unordered_map<string ,int> m;
int n=s.size();
int i=0;
while(i<n)
{
int start=i;
while(i<n&&s[start]==s[i]) i++;
//此时相同字符串的长度为i-start
int len=i-start;
string str(s.begin()+start,s.begin()+i);
for(int k=len;k>=len-2&&k>0;k--)
m[str.substr(0,k)]+=len-k+1; //进行统计
}
//所有相同的字符串都存储到m中了，找长度最长的并且有3个
int ret=-1;
for(auto& [str,k]:m)
{
if(k>=3) ret=max(ret,(int)str.size());
}
return ret;
}
};方法二：分组循环+二分
统计每个独立的相同字符子串的长度。
如果字符x的最长字符串为L1，则其可以形成满足条件的最长子串为：L1-2；
如果字符x的次长字符串为L2，则其可以形成满足条件的最长子串为：
当L1==L2，最长子串是：L1-1；
当L1 > L2，最长子串是：L2；
汇总就是：min(L1-1，L2)。
如果字符x的第三长字符串为L3，则其可以形成满足条件的最长子串为：L3
第四长就不需要考虑了，考虑第三长是因为如果三个子字符串的长度相等，长度就是L3。
class Solution {
public:
int maximumLength(string s) {
unordered_map<char ,vector<int>> m;
int i=0,n=s.size();
while(i<n)
{
int start=i;
while(i<n&&s[i]==s[start]) i++;
m[s[start]].push_back(i-start);
}
int ret=0;
for(auto& [ch,nums]:m )
{
sort(nums.begin(),nums.end(),greater());
nums.push_back(0); //向后面补上两个数据是的数组长度永远大于等于3
nums.push_back(0);
ret=max({nums[2],min(nums[1],nums[0]-1),nums[0]-2,ret});
}
return ret==0?-1:ret;
}
};2576. 求出最多标记下标
题解：排序+同向双指针。返回值最大就是数组长度，这种情况就是数组一分为二，数据前半部分与后半部分一一对应；所以可以先对数组进行排序，使用一个指针指向数组中间位置，一个指向数组尾部，判断中间位置数据的两倍是否大于尾部数据，如果大于是一组，否则说明中间数据太大了，向前走找更小的数据。
class Solution {
public:
int maxNumOfMarkedIndices(vector<int>& nums) {
//先对数组进行排序，再使用同向双指针
int n=nums.size();
sort(nums.begin(),nums.end());
int l=n/2-1,r=n-1,ret=0;
while(l>=0&&r>=n/2)
{
if(2*nums[l]<=nums[r])
{
r--;
ret++;
}
l--;
}
return ret*2;
}
};1898. 可移除字符的最大数目
题解：模拟+二分。如果直接进行挨个删除效率太低，可以同个二分进行优化。先确定给删除的个数，再验证p是不是s的子序列即可。
class Solution {
bool check(string s,string& p,vector<int>& removable,int x)
{
for(int i=0;i<x;i++) s[removable[i]]='0'; //对被删除的位置进行修改
int n=s.size(),m=p.size();
int j=0;
for(int i=0;i<n&&j<m;i++)
if(s[i]==p[j]) j++;
return j==m;
}
public:
int maximumRemovals(string s, string p, vector<int>& removable) {
//如果一个个的进行移除效率太低了
//可以使用二分进行优化
int n=removable.size();
int left=0,right=n+1;
while(left+1<right)
{
int mid=left+(right-left)/2;
if(check(s,p,removable,mid)) left=mid;
else right=mid;
}
return left;
}
};1802. 有界数组中指定下标处的最大值
题解：当直接进行求解比较难得时候考虑在已知答案得情况下能否进行验证。此题如果直接进行求解比较复杂，如果已知index位置得最大数取判断数组总和是否不超过maxSum就很简单，求和时需要用到数列求和的公式。
class Solution {
bool check(int n,int index,long long maxSum,long long t)
{
long long l=index,r=n-index-1;
long long all=0;
if(t>l) all+=t*(t-1)/2-(t-l-1)*(t-l)/2;
else all+=t*(t-1)/2+l-t+1;
if(t>r) all+=t*(t-1)/2-(t-r-1)*(t-r)/2;
else all+=t*(t-1)/2+r-t+1;
return all+t<=maxSum;
}
public:
int maxValue(int n, int index, int maxSum) {
//直接进行模拟难度太大，如果已知最大值进行验证就比较简单了
int left=0,right=maxSum+1;
while(left+1<right)
{
int mid=left+(right-left)/2;
if(check(n,index,maxSum,mid)) left=mid;
else right=mid;
}
return left;
}
};1642. 可以到达的最远建筑
题解：在已知到达的高度的情况下，判断砖和梯子是否够即可；细节：为了找到最优解梯子应该使用在需要砖块最多的位置，所以可以使用一个小堆找出使用最多的梯子。
class Solution {
public:
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
int n=heights.size();
//先将每个房子之间的高度差进行统计
vector<int> heidiff(n-1);
for(int i=1;i<n;i++)
if(heights[i]>heights[i-1]) heidiff[i-1]=heights[i]-heights[i-1];
//进行判断
auto check=[&](int level){
//模拟看能否到达level地方 level-1个间隔
long long all=accumulate(heidiff.begin(),heidiff.begin()+level,0L);
priority_queue<int,vector<int>,greater<int>> pq; //找出ladders个最大的数
for(int i=0;i<level&&ladders>0;i++)
{
if(pq.size()<ladders)
pq.push(heidiff[i]);
else if(pq.top()<heidiff[i])
{
pq.pop();
pq.push(heidiff[i]);
}
}
//进行求和
long long more=0;
while(!pq.empty())
{
more+=pq.top();
pq.pop();
}
return all-more<=bricks;
};
int left=0,right=n;
while(left+1<right)
{
int mid=left+(right-left)/2;
if(check(mid)) left=mid;
else right=mid;
}
return left;
}
};2861. 最大合金数
题解：依旧是验证答案。通过二分来确定答案，再对答案进行检测即可。如果答案的预算太大right-mid，如果答案预算足够left=mid即可。
class Solution {
typedef long long LL;
public:
int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
//判断能否创建ret个合金
auto check=[&](LL ret)
{
for(auto& nums:composition)
{
LL sum=0;
for(int i=0;i<n;i++)
sum+=cost[i]*max(ret*nums[i]-stock[i],(LL)0);
if(sum<=budget) return true;
}
return false;
};
int left=0,right=1e8*2+1; //注意此处上界的取值：及要靠你budegt好要考虑stock
while(left+1<right)
{
int mid=left+(right-left)/2;
if(check(mid)) left=mid;
else right=mid;
}
return left;
}
};总结
二分答案的关键是check函数的编写和上下界的判断，以及什么时候能使用二分，二分既能将题目的思路进行转变-----证明一个答案是否正确，还能让时间复杂度大幅度下降。