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

那么看到二分這兩個字想必我們一定非常熟悉，那么在大學期間的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=log2^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; }
};