概念解釋
概述
? ? ? ? 二分法在算法競賽中一般有這么一個用途：在一個具有單調性的解空間中找到符合題意的一個可行解。下面解釋幾個專有名詞：
解空間
? ? ? ? 很簡單，就是可能存在解的邏輯區域。這個在算法入門時應提到。
可行解
? ? ? ? 符合題意的解
單調性
? ? ? ? 與數學中的基本是一回事。
算法分析
原理
? ? ? ? 就是數學中的逼近原理。通過計算機的高效計算，可以逐步靠近可行解；又由于解空間具有單調性，所以可以簡化枚舉的過程。簡單來講，二分是一種更高效的枚舉手段。
應用
? ? ? ? 我們主要是研究在整數域上的二分。
1.二分查找
? ? ? ? 在一個序列中查找某一個指定的元素，這可以通過二分查找來實現。下面給出一個例子：
? ? ? ? 給出一個整數序列?
?，這個序列有
?個元素。下有
?次詢問，每次會詢問一個整數，請回答該數是否在?
? ? ? ? 這很顯然如果樸素去求，時間復雜度會是?的，在1e5及以上的規模下會TLE。下面考慮二分求解。
? ? ? ? 回憶概念，我們強調，要在一個單調的解空間中尋找答案。所以考慮對這個序列排序；時間復雜度為??。?然后執行以下過程：
- 將區間一分為二；
- 維護區間的中間端點?
?。記錄?
?的值。
- 如果
?，收縮左端點，重復以上步驟；
- 如果
?，收縮右端點，重復以上步驟；
- 直到區間被收縮至只有一個元素，檢查這個元素是否是所求。
? ? ? ? 過程很簡單，時間復雜度也很低，為??。但是這里有很多的細節需要注意，筆者盡量把這些細節全部展示清楚。首先可以先看下面的參考程序，這里選擇結合代碼研究。
? ? ? ??取等問題
? ? ? ? 很簡單，總結出來就一句話：如果中的元素跟?
?有可能取等，那么收縮區間時，區間端點與?
?就取等；反之，不能取等（這時往往+1或者-1）。也就是相鄰，一邊是實心端點，一邊是空心端點。還可以這么看：如果取等，意味著?
?處有可能會是答案，所以收縮區間時，區間端點可以等于?
?。
? ? ? ? 劃分問題
? ? ? ? 也就是考慮??的取值。通常有兩種：
?????????
????????以及
????????
? ? ? ? 區別是：
? ? ? ? 第一種的寫法不會取到?
?，第二種寫法不會取到?
?。進一步地，我們知道，第一種是向下取整，稱為左中位數；第二種向上取整，則是右中位數。我們可以利用這一性質處理無解的問題：設置最初區間分別為：?
?和?
?把一個越界的下標包括起來，如果最后停止在這個下標上，說明無解。當然，第一種適用于找后繼，第二種適用于找前驅。
? ? ? ? STL 函數
? ? ? ? 下面介紹兩個 STL 的函數，分別是 lower_bound()，upper_bound()。這兩個函數分別返回的是在一個單調遞增序列中第一個大于或等于某個數的后繼，以及第一個大于某數的后繼。同樣在下面給出手寫代碼。這里的關鍵就是上面說的劃分問題。
2.二分答案
? ? ? ? 這里主要是兩類問題，最大值最小化以及最小值最大化。也就是判定問題。我們一開始就說過，
???“?通過計算機的高效計算，可以逐步靠近可行解；又由于解空間具有單調性，所以可以簡化枚舉的過程。簡單來講，二分是一種更高效的枚舉手段。”
? ? ? ? 所以歸根結底還是二分查找。請記住：最優化問題往往等價于一個可行性問題的判定。進一步地，是在一個具有嚴格約束的情況下利用二分法枚舉出一個答案來。
? ? ? ? 這句話非常有信息量。我們會給出幾個等價的表述以及幾個例子深刻去理解。
? ? ? ? 有這么幾種表述：
? ? ? ? 建立一個定義域為解空間，值域為0或1的單調分段函數，在這個函數上二分查找分界點。
? ? ? ? 其實本質都是一回事。
? ? ? ? 下面給出幾個例子理解一下。
? ? ? ? 最小值最大化
? ? ? ? 例題：luogu.P2678 [NOIP 2015 提高組] 跳石頭
? ? ? ? 二分所求。找出約束：
“由于預算限制，組委會至多從起點和終點之間移走?M?塊巖石（不能移走起點和終點的巖石）。”
? ? ? ? 也就是說，M 是約束。這樣就容易設計?函數：每次枚舉一個最小值，檢查是否合法。由于這個最小值是具有單調性的，所以可以考慮二分出這個最大值。?
????????最大值最小化
? ? ? ? 例題：luogu.P3853 [TJOI2007] 路標設置
? ? ? ? 二分所求。找出約束：
“以及最多可增設的路標數量”
? ? ? ? 也就是說，路標數量是約束。這樣就容易設計??函數：每次枚舉一個最大值，檢查是否合法。由于這個最大值是具有單調性的，所以可以考慮二分出這個最小值。?
參考程序
在單調遞增序列中查找?
?的最小的元素
//
while(l<r)
{int mid=(l+r)>>1;if(a[mid]<=x) l=mid;else r=mid-1;
}
return a[l];//a[l]==a[r]為終止條件在單調遞增序列中查找?
?的最小的元素
//
while(l<r)
{int mid=(l+r+1)>>1;if(a[mid]>=x) r=mid;else l=mid-1;
}
return a[l];//a[l]==a[r]為終止條件最小值最大化
//
#include<iostream>
using namespace std;
int d[50005];
int l,n,m;
bool check(int k)//我們要二分的是最短跳躍距離
{int last=0,ans=0;for(int i=1;i<=n+1;i++){if(d[last]+k>d[i]) ans++;else last=i;}return ans<=m;//是否滿足約束
}
int main()
{cin>>l>>n>>m;for(int i=1;i<=n;i++)cin>>d[i];d[n+1]=l;int le=0,ri=l*2;while(le<ri)//二分{int mid=(le+ri+1)>>1;if(check(mid)) le=mid;else ri=mid-1;}cout<<le;return 0;
}最大值最小化
//
#include<cstdio>
using namespace std;
int d[100005];
int l,n,k;
bool check(int w)//現在就假設我這里的w就是最大值
{int last=0,ans=0;for(int i=2;i<=n;i++){//while(d[i]>last+w) last+=w,ans++;//我們二分已經是最大距離，如果有比這還大的，那就是要增設 //last=d[i];ans+=(d[i]-d[i-1]-1)/w;}return ans<=k;
}
int main()
{ scanf("%d%d%d",&l,&n,&k);for(int i=1;i<=n;i++)scanf("%d",&d[i]);int le=1,ri=l;while(le<ri){int mid=(le+ri)>>1;if(check(mid)) ri=mid;else le=mid+1;}printf("%d",le);return 0;
}細節實現
? ? ? ? 我們來總結一下二分答案的一般步驟：
- 判斷是否解空間具有單調性——這保證了二分答案的正確性；
- 找出約束條件——這保證了二分的定義域不是無窮的，也就是保證了最值，即解的存在；
- 設計
函數，檢驗枚舉過程中的解是否合法；
- 利用二分查找完成枚舉，得出答案。
? ? ? ? 由此看來，最優化問題在筆者看來不是“構造”出來的，而是真真切切枚舉出來的。在枚舉時，保證枚舉的元素是題目所要求的最大或最小（假設一定是最大/最小值），也就是把被枚舉對象當成一個常量，判斷是否符合約束。所以最優化是枚舉出來的，最大/最小值是約束出來的。
總結歸納
? ? ? ? 二分法的初步應用。日后會有多次更新。
