二分答案法（利用二分法查找區間的左右端點）
（1）估計 最終答案可能得范圍 是什么
（2）分析 問題的答案 和 給定條件 之間的單調性，大部分時候只需要用到 自然智慧
（3）建立一個f函數， 當答案固定的情況下 ，判斷 給定的條件是否達標
（4）在 最終答案可能的范圍上不斷二分搜索， 每次用f函數判斷，直到二分結束，找到最合適的答案
（5）當題目要查找一個區間的左右端點時（符合的區間有多個值找最大或者最小），可以考慮一下這個方法能不能用
綜上：
? ? ? ? 核心點：分析單調性，建立f函數
光說不練，假把式！開練！！！！！
下面有一些相關題目
題目一：愛吃香蕉的珂珂
測試鏈接：875. 愛吃香蕉的珂珂 - 力扣（LeetCode）
題解:
1.????????先看問題答案與對應條件的單調性，這道題中當吃香蕉的速度越大時，吃完所需要的時間就會越少，但這道題中要注意如果一小時內吃完一堆香蕉就會休息，等到下一個小時才會再次開始吃，如果一小時內沒有吃完，那么下一個小時就會繼續吃，吃完之后還是不會繼續吃其他堆的香蕉，還是會休息。所以這個題會用到向上取整算法（ 例如a/b向上取整，(a+b-1)/b ）
2.?????????分析要二分什么，問題要求返回h小時內吃掉所有香蕉的最小速度k（k為整數），那這道題就是二分速度，并且速度與時間也符合單調性，速度也快，時間越短。考慮二分速度的左右區間，左區間 速度最小為1 最大速度為數組中最大數據的大小，因為如果速度大于最大數據時，吃完之后也不會繼續吃下一堆還是會休息，又有單調性所以最大數據的速度一定可以，但不會是答案。
3.? ? ? ? check函數，參數傳速度，返回吃完所需要的時間，然后與給定的k作對比，不斷的縮小范圍直到二分結束，返回答案。
class Solution {
public:int minEatingSpeed(vector<int>& piles, int h) {//定區間int r = 0;//找到數組中最大的數據作為區間的右端點for(int i=0; i<piles.size();i++){r = max(piles[i],r);}int ans = 0;//速度最小為1，左端點設置為1int l = 1;int mid =0;while(l<= r){// 等價于mid = (l+r)/2 但有時會越界防止越界mid = l+((r-l)>>1); // 二分點靠左if(check(piles,mid) <= h){//達標//記錄答案ans = mid;r = mid-1;}else{//不達標//不記錄答案直接去右面二分l = mid+1;}}return ans;}//check函數檢查是否符合要求long long check(vector<int>& piles, int mid){//時間是向上取整 ，初始化long long類型數據，防止數據過大越界long long ans = 0; // ans為時間int i = 0;int size = piles.size();while(size--){// 時間是向上取整的ans += (piles[i++]-1)/mid + 1;}//返回mid速度，吃完所需時間return ans;}
};題目二：分割數組的最大值
題目鏈接：410. 分割數組的最大值 - 力扣（LeetCode）?（畫匠問題）
題解：
1.? ? ? ? 總結題意就是將數組分成規定的份數，然后返回分好的這些組中各自和的最大值的最小（就是組內的和最大的組的和使這個數即可能的小返回最小）
2? ? ? ? 先看看這道題中最終答案，與給定條件之間是否存在單調性，最答案是各自總和的最大值，給定條件為劃分成幾份，當劃分的分數越多，各自的總和就會越小，存在一定的單調性。
3.? ? ? ? 思路就是寫一個函數，傳遞的參數就是各自總和的最大值，然后返回滿足在這個限制下，會將數組分成幾份，然后與給定的k作對比，不斷地縮小區間，直至二分結束
方法一：
????????在后面check函數中處理特殊情況（容易忘記處理）
class Solution {
public:int splitArray(vector<int>& nums, int k) {//二分答案 將最大部分的累加和一直二分，寫一個函數（每組數據都限制在這個累加和的范圍內時是否符合要求小于等于k個）判斷//非負整數可以為0//在前面可以將區間縮小到最小然后可以避免后面細節的判斷防止出錯//改法將左端點設置為最小0int l = 0;//二分區間的右端點，就是累計和的最大也就是將數組分成一份就是數組中所有元素的累加和 int r = 0;for(int i = 0; i<nums.size();i++){r += nums[i];}//起始將mid設為0 int mid = 0;//ans來記錄二分的答案，當答案滿足記錄下來繼續二分 int ans = 0;//確定了二分的大致范圍while(l<=r){//mid = (r+l)/2 下面這樣寫可以防止越界超過int的最大數值 mid = l+((r-l)>>1);//下面可以這樣理解，返回值小于<=k,就是符合限制條件并且分的分數還比規定的小，那么一定有mid if( check(nums,mid) <= k){//mid都符合要求，右面的limit一定符合要求，所以去左面進行二分查找//先記錄答案，然后去做左面看有沒有最優解ans = mid;r = mid-1;}else{//不符合要求，去右面找 l = mid +1;}}return ans;}//可以說用到了貪心算法，就是沒個部分都是最優解，這樣分的份數最小 int check(vector<int>& nums, int limit){int sum = 0;int ret= 1; //代表最少分幾份for(int i = 0 ;i<nums.size();i++){//如果數組中有值超過了限制，這個限制不成立if(nums[i] > limit) return INT_MAX;if(sum + nums[i] <= limit){//沒有滿 將數據吸納進來sum += nums[i];}else{//當前sum結束了，現在sum的值為當前num[i]的值ret++;sum = nums[i];}}return ret;}
};方法二：
? ? ? ? 在前面劃分左右區間時就將區間范圍劃分到最小，這樣可以避免處理后面，數組中有大于限制情況。
class Solution {
public:int splitArray(vector<int>& nums, int k) {//二分答案 將最大部分的累加和一直二分，寫一個函數（每組數據都限制在這個累加和的范圍內時是否符合要求小于等于k個）判斷//非負整數可以為0//在前面可以將區間縮小到最小然后可以避免后面細節的判斷防止出錯int l = 0;int r = 0;for(int i = 0; i<nums.size();i++){r += nums[i];//區間的左值因為是數組劃分完后的最大的最小值，所以一定大于等于數組中最大元素的值，將左端點設置為數組中最大的元素l = max(l,nums[i]);}int mid = 0;int ans = 0;//確定了二分的大致范圍while(l<=r){mid = l+((r-l)>>1);if( check(nums,mid) <= k){//mid都符合要求，右面的limit一定符合要求，所以去左面進行二分查找//先記錄答案，然后去做左面看有沒有最優解ans = mid;r = mid-1;}else{l = mid +1;}}return ans;}int check(vector<int>& nums, int limit){int sum = 0;int ret= 1; //代表最少分幾份for(int i = 0 ;i<nums.size();i++){if(sum + nums[i] <= limit){//沒有滿 將數據吸納進來sum += nums[i];}else{//當前sum結束了，現在sum的值為當前num[i]的值ret++;sum = nums[i];}}return ret;}
};題目三：找出第K小的數對距離
題目鏈接：719. 找出第 K 小的數對距離 - 力扣（LeetCode）
題解：
1? ? ? ? 題意數對距離就是兩數之間的絕對值差值，題目要返回第k小的數對距離。
2? ? ? ? 先看答案與給定條件之間的單調性關系，當兩數的絕對值差值越大，那么這個K值也會越大，所以存在一定的單調性關系。
3? ? ? ? 那么我們可以二分數對距離，根據題意找到最大最小的數對距離。
4? ? ? ? ?check函數我們可以傳遞mid位置的數對距離，然后返回mid位置為第幾小的位置，與給定的k進行比較，直到二分結束。
class Solution {
public:int smallestDistancePair(vector<int>& nums, int k) {//因為要找數據之間差值最大的兩個數，并且該題排序與不排序不會影響最終結果 sort(nums.begin(),nums.end());//由于上面進行了排序所以右邊界就是最大值與最小值的差值 int r = nums[nums.size() -1] - nums[0];//左邊界就是數組中最小的差值，也就是數組之間相鄰的兩個數據最小的差值int l =r;for(int i = 1;i<nums.size()-1;i++){l = min(r,nums[i]-nums[i-1]);} int ans = 0;int mid = 0;while(l<=r){mid = l+((r-l)>>1);//num為返回的第幾小的元素，與k進行比較int num = check(nums,mid);if(num >= k){//符合要求，將mid記錄，這是mid可能已經為最終答案，記錄以備候選，繼續二分看是否還有最優解 ans = mid;r = mid -1;}else{//mid不符合要求，縮小區間到mid的右面 l = mid +1;}}return ans;}//用來判斷是不是與第k小的關系，也就是返回<=mid的數對數量int check(vector<int>& nums,int mid){//這道題應用到了滑動窗口的方法 int sum = 0;int r = -1, l = 0;for(l=0;l< nums.size();l++){//從0開始存不能等于nums.size(),如果r+1 - l 的差值小于等于傳進來的差值，就r++向后走，否則就停止 while(r < l || ((r+1)<nums.size() && nums[r+1] - nums[l] <= mid)){r++;}//因為l要加了，先將區間內符合條件的數據記錄個數，L++，也就是l走之前記錄l位置處的符合條件的個數 sum += r-l;}return sum;}
};
