二分算法篇：二分答案法的巧妙应用

二分算法篇：二分答案法的巧妙应用

那么看到二分这两个字想必我们一定非常熟悉，那么在大学期间的c语言的教学中会专门讲解二分查找，那么我们来简单回顾一下二分查找算法，我们知道二分查找是在一个有序的序列中寻找一个数在这个序列的位置，那么我们可以用二分查找来应用，那么二分查找的算法的原理就是我们在这个有序区间[l,r]中寻找目标数x，那么我们从中间位置mid处去匹配，如果mid处的值大于x，那么意味着mid处之后的值也一定大于我们的x(假设是一个升序序列),那么我们去左半边l到mid-1区间处匹配，如果小于x，那么mid处之前的位置也一定小于我们的x，那么我们就去右半边的区间mid+1到r区间去匹配，每次都取中点位置与x进行比较然后确定下一次搜索的折半区间，直到我们的区间长度只剩1或者中点处的值等于我们的mid

代码实现：

int get(int l,int r,int target)
{if(l<=r){int mid=l+(r-l)/2 //写成(l+r)/2 可能会有溢出风险if(mid==target){return mid;}else if(mid>target){return get(l,mid-1,target);}else{return get(mid+1,r,target);}
}
return -1;
}

那么知道了二分查找的原理那么我们分析一下这个算法的时间复杂度，那么假设我们的区间长度是n，那么我们最坏的情况也就是我们整个区间都没有我们的目标值x，那么意味着我们会将整个区间不断的二分直到区间长度为1，那么我们也就可以建立一个等式假设我们二分的总次数是m，那么每一次会将区间的长度给折半直到为1，每次折半就是区间长度不断除以2，除了m次最后得到1，那么反过来就是我们区间长度为1不断乘以2乘了m次得到长度n，所以就有
$$2^m=n$$
再两边同时取对数则可以得到：
$$m=log{2}^n$$
所以我们二分算法的时间复杂度是log2^n,那么这个时间复杂度是非常优秀的了，假设我们的n是21亿的话，那么总共要二分的次数也就32次，但是我们二分查找有一个局限那就是我们的数据集必须是要有序的

但是我们的二分算法可不止于此，很多人以为所谓的二分就是我们c语言学的二分查找那么简单，二分在我眼里它可不仅仅是一个所谓具体的一个算法，而是一种思想，刚才的二分查找可谓是给你端上了一份开胃菜，那么真正的大餐就在我们的下文当中

1.二分原理

那么我们二分算法，很多人认为我们只有一个数据集是有序或者更贴切的说数据集是具有单调性的，那么才可以应用我们的二分。

那么所谓的单调性，我们可以用数学中的一次函数来理解，那么我们知道一次函数是一个直线，那么根据其斜率的正负，那么斜率大于0，那么该一次函数的y值是随着x的增长而递增，反之小于0则是递减，那么我们的一次函数就是具有单调性的一个函数，那么我们的数据集就好比是在这个一次函数的直线上的一个个点，那么我们二分就是在这个直线上取一个点，看该点和我们的答案之间的关系，如果该点小于我们的答案，那么我们就到在沿着直线往上寻找，反之则往下寻找，那么这就是单调性。

那么话虽没错，我们数据集具有某种单调性我们可以应用二分，但是我们能二分的场景，不一定一定要具有单调性，那么我们的二分更为关键的应用，那么就是寻找一个性质的边界：

那么对于一个我们要寻找的答案来说，答案如果具有一个区间假设是[L,R],那么该区间那么可以按照某个性质将我们这个区间给分成了左右两部分，那么我们的二分就可以分别寻找着左右两部分的性质的边界，那么其中我们可以寻找左半边性质的右边界，以及右半边性质的左边界，这里左右半边的边界是肯定不能重合的，因为我们该性质将该区间分为两个部分，也就是这个区间中的每个点只能拥有这两个性质中的其中一个，不可能同时具备两个性质，所以，我们左右边界是不可能重合的。

那么我们找这两个边界，我们有两种方式，分别是整数二分以及浮点数二分，那么这个两种方式都有固定的模版，那么我们先来讲解一下整数二分：

那么我们首先来寻找右区间的左边界，那么我们不知道我们这个左边界的具体位置究竟是哪里，那么我们就得通过二分的方式来逐渐逼近，那么怎么逼近呢？

那么我们每次都取要搜索区间[L,R]的中点mid，然后得定义一个check函数，那么该函数就是检验这个区间中的任意一点是否满足右区间的性质，那么有了check函数，那么如果我们该中点mid是满足我们的右区间的性质的话，那么我们check函数会返回一个true，反之如果该中点不满足右区间的性质而是满足左区间的性质的话则返回一个false，那么如果我们将该中点mid代入check函数之后，返回的是一个true，那么确定从mid到R这个区间是我们的右区间，那么我们的右区间的左边界只可能在mid的左侧，不可能在右侧，所以我们就得去L到mid区间处继续二分，所以我们要搜索的区间就是[L,mid]，这里的mid替换我们的R，注意这里我们一定要取到mid而不是mid-1，因为我们这里的区间是左闭右闭的区间，那么我们如果是左开右开的话，那就是mid-1。

那么如果我们的check函数返回的是false，那么说明我们该中点mid不满足右区间的性质，那么我们右区间的左边界一定在mid之后，并且取不到mid，所以我们就到右侧mid+1到R处继续二分，那么直到区间长度为1，从而找到该边界点

同理

对于寻找左区间的右边界，那么我们还是一样的思路，定义一个check函数，那么从中点处检验，如果满足该左边界的性质，那么则返回true，那么说明我们的右边界只可能出现在mid的右侧，也就是在区间[mid,R]位置处，如果返回false，那么mid位置处不满足左区间的性质，那么只能在[L,mid-1]处继续去二分

那么寻找右区间的左边界的代码板子如下：

//寻找右边界的左边界
while(l<r)
{int mid=(l+r)/2;if(check(mid)){r=mid;}else{l=mid+1;}
}

寻找左区间的右边界的代码板子：

//寻找左边界的右边界
while(l<r)
{int mid=(l+r+1)/2;/*这里假设我们的l=r-1，那么如果是(l+r)/2的话，那么向下取整，结果会是l，会死循环，所以为了避免这个情况会加1，得到结果是r*/if(check(mid)){l=mid;}else{r=mid-1;}
}

浮点数二分：

而我们浮点数二分的思路和我们整数二分的思路是一样的，只不过相比于整数二分，我们浮点数二分由于精度更高，那么我们每次二分划分的边界点更为精确，那么如果我们最终二分的区间已经很小趋近于0的时候，那么我们就确认找到了边界点：

代码板子：

while(l<r)
{int mid=(l+r)/2；if(check(mid)){l=mid;}else{r=mid-1;}
}

---

2.二分答案法原理

那么有了我们刚才的二分的原理，那么这里我们就可以来了解所谓的二分答案法是什么了，那么二分答案发是一个利用二分来求解答案的算法：

那么如果我们发现我们该题目的要最终求解的答案明显有一个明确的区间[L,R],

并且答案与我们的题目所给的条件具有一种单调性的关系，那么我们就可以定义一个性质，然后该性质将我们的答案所在的区间[L,R]给分成了左右两部分区间，其中这两部分要么左区间要么是满足该性质，右区间则是不满足该性质所以将整个区间一分为二或者则是左区间不满足该性质但右区间满足该性质。

所以我们得根据我们答案与题目所给的条件之间具备的单调性来判断我们满足该性质的区间究竟是左区间还是右区间，确定之后，我们在利用我们的二分，依据该题所编写的check函数来检验中点mid的值是否满足我们定义的该性质，从而确定去哪个区间进行二分，然后不断二分逐步逼近边界点直到找到这个边界点，而整个二分答案法流程中的最难的一步便是我们性质的定义，有的难题它的要定义的性质你很难想得到，那么性质想不到会导致我们核心的check函数你写不出来，那么这个题也就根本做不出来了，那么我们只有多连续见得多了才能对这个check函数的编写得心应手。

那么这就是我们的二分答案法的思想，那么我们该题能否应用二分答案法的特征就是是否答案有明确的区间并且答案与题目条件是否具备单调性，那么满足该特征则可以用我们的二分答案法。

那么我们二分答案法只要也就是解决最大值最小化或者最小值最大化等等问题，我们具体能不能使用二分答案法核心还是得看我们对于题目的条件的理解与分析。

那么接下来我就会通过几个例题来具体实战一下，看看我们这些题是怎么观察分析以及如何应用我们上面那套二分答案法的流程的。

3.应用实战

题目一：爱吃香蕉的珂珂 难度：EZ

题目分析：那么这里我们知道我们这道题要求我们的最小且满足题目要求的速度，那么这里速度是我们要求的答案，那么我们分析一下题目的条件，我们其实不难发现，我们的速度是有一个明显的区间，那么每堆香蕉最少只有1个，那么也就意味着我们的速度可以是1，那么速度最大则是这n堆香蕉的最大值，因为我们知道无论速度比这个值还大，那么我们一小时再怎么快速吃完该堆香蕉只能陷入等待，等到下一小时吃下一堆，也就意味着如果速度比这还大，那么它对时间的缩短没有任何贡献了，所以我们确定了我们的答案也就是速度所在的区间是在[1,max(piles[i])]中，那么我们接下来来分析一下答案是否存在某种单调性，我们发现这里我们速度越大，那么我们吃香蕉的时间只会缩短或者不变，反之速度越小，那么时间只会变长，那么速度越大，时间变短或者不变，那么也就意味着它越容易在警卫离开的h小时内吃完。

所以我们这里根据前面的分析，那么便可以定义性质，也就是我们在该速度下，能够在h小时内吃完所有的香蕉，那么我们根据我们的单调性，我们速度越大，越容易在h小时内吃完所有的香蕉，那么意味着我们满足该性质的一定是这个答案区间的右区间而不是靠左的左区间，那么我们接下来就是寻找右区间的左边界，那么这个左边界就是我们这个题的答案，那么我们根据这个性质来实现一个check函数来检验一下mid是否满足该性质，满足返回true，不满足返回false，至于二分的过程就是我们上文所讲的原理，而具体实现check函数的细节，我这里也就不再赘述了

代码实现：

class Solution {
public:
bool check(int x,int h,vector<int>&piles)
{long long sum=0;for(int i=0;i<piles.size();i++){sum+=(piles[i]+x-1)/x;}if(sum>h){return false;}return true;
}int minEatingSpeed(vector<int>& piles, int h) {int l=1,r=0;for(int i=0;i<piles.size();i++){if(piles[i]>r){r=piles[i];}}while(l<r){int mid=(l+r)/2;if(check(mid,h,piles)){r=mid;}else{l=mid+1;}}return l;}
};

那么这里我们看看这个题是不是应用了我们刚才说的那套流程，也就是发现我们的答案存在某个区间，然后分析答案的单调性，根据单调性定义性质写出check函数，然后二分，那么这就是我们二分答案法的一个分析的思维模式以及套路：

1.确定答案所在区间[L,R]

2.分析答案的单调性

3.根据单调性定义性质

4.根据性质写出二分答案法核心的check函数

5.不断二分寻找边界

题目二：画家 难度：HARD

题目：现在我们有k个画匠，那么我们有n幅画需要画匠完成，其中每幅画完成的时间为n[i] (0<=i<n)分钟，那么我们每一个画家只能完成连续的m幅画，也就是说我们其中一个画家可以分配完成第一幅以及第二幅画，但是不能分配完成第一幅以及第三幅画因为不是连续的，那么我们画家同时画画，那么我们整个n幅画完成的时间就是这k个画家中其中一个完成的最长的那个时间，那么我们可以不用分配所有画家去做画，可以只分配一个画家或者全部画家，并且每个画家分哪些画都是我们自己确定，那么问我们k个画家完成这n幅画的最短时间是多少？

题目分析：

那么这个题我们这里我们要求完成这n幅画的最短时间，那么我们就是要让每个画家的完成时间尽可能的短，那么我们仔细分析题目的条件，那么我们发现我们的每个画家作画时间也是有一个区间的，那么我们的画可以是0幅，那么我们可以不用分配画家，那么理轮上画家的完成时间可以是0，同时我们也可以只分配一个画家，那么画家的完成时间则是所有画的总时间，那么我们便得到了画家的作画时间的一个区间[0,sum(n[i])]，那么我们再来分析一下作画时间的单调性，那么我们如果给一个画家分配的时间越多，那么意味着我们画完这n幅画所需要的画家的数量就越少，那么同理，如果每个画家分配的时间越少，那么我们画完这n幅画所需要的画家的数量就越多，那么有了这个单调性我们便可以定义我们的性质：每个画家作画的时间不超过t分钟，我们能分配不超过k个画家来完成这n幅画。

那么我们可以利用这个性质将我们的答案区间给一分为二，那么根据我们刚才分析的单调性，我们一个画家分配时间越多，那么画完这n幅画所分配的画家的数量越小，那么也就意味着我们画家作画时间越长，那么越能够满足我们这个性质，所以我们确定我们满足这个性质的区间是右区间，那么题目的答案也就是得到右区间的左边界，那么我们写一个check函数来检验中点mid是否满足该性质，来进行二分即可

代码实现：

class Solution {
public:
bool check(int x,int k,vector<int>&time)
{int ans=1;int temp=0;for(int i=0;i<time.size();i++){if(time[i]>x){return false;//如果本身该幅画的时间就超过了每个画家的最大分配时间，那么直接返回false}if(temp+time[i]>x){ans++;temp=time[i];}else{temp+=time[i];}}if(ans<=k){return true;}
}int minTime(vector<int>& time, int k) {int l=0,r=0;for(int i=0;i<time.size(),i++){r+=time[i];}while(l<r){int mid=(l+r)/2;if(check(mid,k,time)){r=mid;}else{l=mid+1;}}return l;}
};

题目三：机器人跳跃 难度：MID

题目：现在有一个机器人，它要跨越n个平台，那么这n个平台中每个平台的高度为H[i] (0<=i<n),那么我们机器人能够跳跃一个平台的前提条件就是我们这个机器人的能量值k要大于等于该平台的高度，那么就能跳跃过去，并且成功跳跃该平台，机器人的能量值k会加上能量值与平台高度的差值k-H[i]，那么现在机器人在跳跃第一个平台之前有一个初始能量值k，那么问初始能量值最小为多少能够让机器人跨越所有平台？

题目分析：那么我们根据题意，机器人如果能量值比平台高，那么不仅能跨越并且能量值还能够得到增长，那么也就意味着我们机器人的能量值越高，那么它更有能力跨越平台，并且还能获得增长，那么能量值越高一定是不吃亏的，反而能量值越低，会有风险跨不过平台，并且增长还少，那么根据这个分析，我们就找到我们要确定的答案也就是能量值的一个单调性了，那么我们看看我们这个能量值的区间，理论上，我们能量值的最小值可以为0，假设平台的高度都为0，那么最大值的话能量值最大就只需要达到所有平台的最大高度即可，因为达到这个高度根据题意，我们就必定足够跨越所有平台，即使不加能量的增长，那么我们的能量值的区间[0,max(H[i])],那么我们在根据我们之前的单调性定义性质：机器人在该能量值下，能够跨越所有平台。

那么这个性质能够将我们的区间一分为二，并且右区间是满足我们的性质，那么这题的答案就是寻找我们右区间的左边界，那么我们根据这个性质来编写我们的check函数。

但是这道题我要对check函数的实现提一嘴，这里我们的能量的增长可以是指数级的，假设我们的平台高度都是2，那么我们的初始能量值是4，那么我们每次增加的能量值是2,4,8,16，那么我们如果这个平台的数量过长，那么我们只打我们这里的能量值的增长是一个以2的n次方的速度增长，那么指数级的增长是很快的，那么就会导致我们最后的能量值我们用int或者long类型接收都会出现溢出的风险，所以这里是一个陷阱，我们在实现check函数的时候，当我们的能量值已经达到和最大平台高度一样的时候，我们就确定它能够跨越玩所有的，不用在依次往后遍历，所以在check函数的实现要注意

代码实现：

class Solution {
public:
bool check(int k,int max,vector<int>&height)
{for(int i=0;i<height.size();i++){if(k<height[i]){return false;}if(k>=max){return true;}k+=(k-height[i]);}return true;
}int minEnerge(vector<int>& height, int k) {int l=0,r=0;for(int i=0;i<time.size(),i++){r=max(height[i],r);}while(l<r){int mid=(l+r)/2;if(check(mid,r,height)){r=mid;}else{l=mid+1;}}return l;}
};

题目四：第k小 难度：HARD

题目:现在有一个整数序列num，那么我们这个序列当中的两个不同位置的数num[i]和num[j] (i!=j)可以组成一个数对，那么这个数会得到一个得到一个差值，这个差值是绝对值，那么我们这个数对当中各个不同的数对的差值可以排序，那么我们要求其中第k小的差值是什么？

例：[1,2,1]

[1,2]->1

[1,1]->0

[2,1]->1

第一小的差值是0

题目分析：那么这里我们首先可以得到这个差值的区间，那么最小只能是0，那么最大则是我们这个序列中最大是减去最小数得到，那么我们可以首先对整个序列排序然得到差值的最大值，那么这个差值的最大值的区间就是[0,max-min],那么这个题其实最难想的就是性质的定义，因为这题差值的单调性的具体含义是比较难想，这个题的关键就是我们对于一个差值假设差值为m，那么我们在这个序列中差值为m的数对可能不只有一个，就在上面的以数组[1,2,1]为例子中，我们差值为1的数对有两个，那么假设我们这个差值为m是我们这个序列的第k小的差值，那么意味着我们前面比我们这个差值m还要小的差值有k-1个，那么同理对于前面比m还要小的k-1个差值，每一个差值所对应的数对也至少有一个对应的数对，那么意味着我们包括前面k-1个差值的数对和当前第k小差值的数对加起来总的数对的数量，它一定是大于等于k个的，那么你的差值越大，那么对应的总数对的数量一定会增多，反之差值越小，对应的总数对一定越少

那么我们可以这样定义我们的性质：在差值不超过m的情况下，我们的数对的数量大于等于k个

那么我们可以将这个区间一分为二，然后右区间是满足性质的区间，那么我们就写一个check函数来验证在不超过该MID值下，我们的数对的数量是否大于等于k，这里我们对数组进行了排序，那么我们可以利用滑动窗口来计数实现check函数。

那么这个题难就在难在这个性质的得到以及如何写check函数。

代码实现：

class Solution {
public:// 检查函数，判断差值不超过mid的数对数量是否大于等于kbool check(int mid, vector<int>& nums, int k) {int count = 0;int n = nums.size();int j = 0;// 使用滑动窗口计算数对数量for (int i = 0; i < n; i++) {while (j < n && nums[j] - nums[i] <= mid) {j++;}count += j - i - 1; // 计算以i为起点的数对数量if (count >= k) {return true;}}return count >= k;}int smallestDistancePair(vector<int>& nums, int k) {sort(nums.begin(), nums.end()); // 对序列进行排序int l = 0, r = nums.back() - nums.front(); while (l < r) {int mid = l + (r - l) / 2; // 计算中点if (check(mid, nums, k)) {r = mid; // 缩小右边界} else {l = mid + 1; // 扩大左边界}}return l; }
};

4.结语

那么本文就讲述了我们的二分答案法，那么看完本篇文章，我觉得你应该收获了如何写二分的一个模本，以及二分答案法的流程，但是我想说的是算法的学习，可不仅仅学会了原理就够了，还要自己下去不断练习