本系列是這本算法教材的擴展資料：《算法競賽入門到進階》. 羅勇軍、郭衛斌. 清華大學出版社
二分法和三分法是算法競賽中常見的算法思路，本文介紹了它們的理論背景、模板代碼、典型題目。
1. 二分法的理論背景
在《計算方法》教材中，關於非線性方程的求根問題，有一種是二分法。
方程求根是常見的數學問題，滿足方程：
f(x) = 0 (1-1)
的數x』稱為方程(1-1)的根。
所謂非線性方程，是指f(x)中含有三角函數、指數函數或其他超越函數。這種方程，很難或者無法求得精確解。不過，在實際應用中，只要得到滿足一定精度要求的近似解就可以了，此時，需要考慮2個問題：
（1）根的存在性。用這個定理判定：設函數在閉區間[a, b]上連續，且f(a) ∙ f(b) < 0,則f(x) = 0存在根。
（2）求根。一般有兩種方法：搜索法、二分法。
搜索法：把區間[a, b]分成n等份，每個子區間長度是∆x，計算點xk = a + k∆x (k=0,1,2,3,4,…,n)的函數值f(xk)，若f(xk) = 0，則是一個實根，若相鄰兩點滿足f(xk) ∙ f(xk+1) < 0，則在(xk, xk+1)內至少有一個實根，可以取(xk+ xk+1)/2為近似根。
二分法：如果確定f(x)在區間[a, b]內連續，且f(a) ∙ f(b) < 0，則至少有一個實根。二分法的操作，就是把[a, b]逐次分半，檢查每次分半後區間兩端點函數值符號的變化，確定有根的區間。
什麼情況下用二分？兩個條件：上下界[a, b]確定、函數在[a, b]內單調。
複雜度：經過n次二分後，區間會縮小到(b - a)/2n。給定a、b和精度要求ε，可以算出二分次數n，即滿足(b - a)/2n <ε。所以，二分法的複雜度是O(logn)的。例如，如果函數在區間[0, 100000]內單調變化，要求根的精度是10-8，那麼二分次數是44次。
二分非常高效。所以，如果問題是單調性的，且求解精確解的難度很高，可以考慮用二分法。
在算法競賽題目中，有兩種題型：整數二分、實數二分。整數域上的二分，注意終止邊界、左右區間的開閉情況，避免漏掉答案或者死循環。實數域上的二分，需要注意精度問題。
2. 整數二分模板
2.1 基本形式
先看一個簡單問題：在有序數列a[]中查找某個數x；如果數列中沒有x，找它的後繼。通過這個問題，給出二分法的基本代碼。
如果有x，找第一個x的位置；如果沒有x，找比x大的第一個數的位置。
示例：
a[] = {-12,-6,-4,3,5,5,8,9}，其中有n = 8個數，存儲在a[0]～a[7]。
1)查找x = -5，返回位置2，指向a[2] = -4；
2)查找x = 7，返回位置6，指向a[6] = 8；
3)特別地，如果x 大於最大的a[7] = 9，例如x = 12，返回位置8。由於不存在a[8]，所以此時是越界的。
下面是模板代碼。
查找大於等於 x的最小的一個的位置（x或者x的後繼）
int bin_search(int *a, int n, int x){ //a[0]～a[n-1]是單調遞增的
int left = 0, right = n; //注意：不是 n-1
while (left < right) {
int mid = left + (right-left)/2; //int mid = (left + right) >> 1;
if (a[mid] >= x) right = mid;
else left = mid + 1;
} //終止於left = right
return left; //特殊情況：a[n-1] < x時，返回n
}
下面對上述代碼進行補充說明：
（1）代碼執行完畢後，left==right，兩者相等，即答案所處的位置。
（2）複雜度：每次把搜索的範圍縮小一半，總次數是log(n)。
（3）中間值mid
中間值寫成mid = left + (right-left)/2 或者mid = (left + right) >> 1都行 [參考李煜東《算法競賽進階指南》26頁，有mid = (left + right) >> 1的細節解釋]。不過，如果left + right很大，可能溢出，用前一種更好。
不能寫成 mid = (left + right)/2; 在有負數的情況下，會出錯。
（4）對比測試
bin_search()和STL的lower_bound()的功能是一樣的。下面的測試代碼，比較了bin_search()和lower_bound()的輸出，以此證明bin_search()的正確性。注意，當a[n-1]<key時，lower_bound()返回的也是n。
代碼執行以下步驟：
1）生成隨機數組a[]；
2）用sort()排序；
3）生成一個隨機的x；
4）分別用bin_search()和lower_bound()在a[]中找x；
5）比較它們的返回值是否相同。
bin_search()和lower_bound()對比測試
#include<bits/stdc++.h>
using namespace std;
#define MAX 100 //試試10000000
#define MIN -100
int a[MAX]; //如果MAX超過100萬，大數組a[MAX]最好定義為全局。
//大數組定義在全局的原因是：有的評測環境，棧空間很小，大數組定義在局部佔用了棧空間導致爆棧。
//現在各大OJ和比賽都會設置編譯命令使棧空間等於內存大小，不會出現爆棧。
unsigned long ulrand(){ //生成一個大隨機數
return (
(((unsigned long)rand()<<24)& 0xFF000000ul)
|(((unsigned long)rand()<<12)& 0x00FFF000ul)
|(((unsigned long)rand()) & 0x00000FFFul));
}
int bin_search(int *a, int n, int x){ //a[0]～a[n-1]是有序的
int left = 0, right = n; //不是 n-1
while (left < right) {
int mid = left+(right-left)/2; //int mid = (left+ right)>>1;
if (a[mid] >= x) right = mid;
else left = mid + 1;
}
return left; //特殊情況：如果最後的a[n-1] < key，left = n
}
int main(){
int n = MAX;
srand(time(0));
while(1){
for(int i=0; i< n; i++) //產生[MIN, MAX]內的隨機數，有正有負
a[i] = ulrand() % (MAX-MIN + 1) + MIN;
sort(a, a + n ); //排序，a[0]~a[n-1]
int test = ulrand() % (MAX-MIN + 1) + MIN; //產生一個隨機的x
int ans = bin_search(a,n,test);
int pos = lower_bound(a,a+n,test)-a;
//比較bin_search()和lower_bound()的輸出是否一致：
if(ans == pos) cout << "!"; //正確
else { cout << "wrong"; break;} //有錯，退出
}
}
2.2 STL的lower_bound()和upper_bound()
如果只是簡單地找x或x附近的數，就用STL的lower_bound()和upper_bound()函數。有以下情況：
（1）查找第一個大於x的元素的位置：upper_bound()。代碼例如：
pos = upper_bound(a, a+n, test) - a;
（2）查找第一個等於或者大於x的元素：lower_bound()。
（3）查找第一個與x相等的元素：lower_bound()且 = x。
（4）查找最後一個與x相等的元素：upper_bound()的前一個且 = x。
（5）查找最後一個等於或者小於x的元素：upper_bound()的前一個。
（6）查找最後一個小於x的元素：lower_bound()的前一個。
（7）單調序列中數x的個數：upper_bound() - lower_bound()。
2.3 簡單例題
尋找指定和的整數對。這是一個非常直接的二分法問題。
∎問題描述
輸入n ( n≤100,000)個整數，找出其中的兩個數，它們之和等於整數m(假定肯定有解)。題中所有整數都能用int 表示。
∎題解
下面給出三種方法：
（1）暴力搜，用兩重循環，枚舉所有的取數方法，複雜度O(n^2)。超時。
（2）二分法。首先對數組從小到大排序，複雜度O(nlogn)；然後，從頭到尾處理數組中的每個元素a[i]，在a[i]後面的數中二分查找是否存在一個等於 m - a[i]的數，複雜度也是O(nlogn)。兩部分相加，總複雜度仍然是O(nlogn)。
（3）尺取法/雙指針/two pointers。對於這個特定問題，更好的、標準的算法是：首先對數組從小到大排序；然後，設置兩個變量L和R，分別指向頭和尾，L初值是0，R初值是n-1，檢查a[L]+a[R]，如果大於m，就讓R減1，如果小於m，就讓L加1，直至a[L]+a[R] = m。排序複雜度O(nlogn)，檢查的複雜度O(n)，總複雜度O(nlogn)。檢查的代碼這樣寫：
void find_sum(int a[], int n, int m){
sort(a, a + n - 1); //先排序
int L = 0, R = n - 1; //L指向頭，R指向尾
while (L < R){
int sum = a[L] + a[R];
if (sum > m) R--;
if (sum < m) L++;
if (sum == m){
cout << a[L] << " " << a[R] << endl; //列印一種情況
L++; //可能有多種情況，繼續
}
}
}
3. 整數二分典型題目
上面給出的二分法代碼bin_search()，處理的是簡單的數組查找問題。從這個例子，我們能學習到二分法的思想。
在用二分法的典型題目中，主要是用二分法思想來進行判定。它的基本形式是：
while (left < right) {
int ans; //記錄答案
int mid = left+(right-left)/2; //二分
if (check(mid)){ //檢查條件，如果成立
ans = mid; //記錄答案
… //移動left（或right）
}
else … //移動right（或left）
}
所以，二分法的難點在於如何建模和check()條件，其中可能會套用其他算法或者數據結構。
二分法的典型應用有：最小化最大值、最大化最小值。
3.1 最大值最小化（最大值儘量小
3.1.1序列劃分問題
這是典型的最大值最小化問題。
∎題目描述
例如，有一個序列{2,2,3,4,5,1}，將其劃分成3個連續的子序列S(1)、S(2)、S(3)，每個子序列最少有一個元素，要求使得每個子序列的和的最大值最小。
下面舉例2個分法：
分法1：S(1)、S(2)、S(3)分別是(2,2,3)、(4,5)、(1),子序列和分別是7、9、1，最大值是9；
分法2：(2,2,3)、(4)、(5,1),子序列和是7、4、6，最大值是7。
分法2更好。
∎題解
在一次劃分中，考慮一個x，使x滿足：對任意的S(i)，都有S(i)<=x，也就是說，x是所有S(i)中的最大值。題目需要求的就是找到這個最小的x。這就是最大值最小化。
如何找到這個x？從小到大一個個地試，就能找到那個最小的x。
簡單的辦法是：枚舉每一個x，用貪心法每次從左向右儘量多劃分元素，S(i)不能超過x，劃分的子序列個數不超過m個。這個方法雖然可行，但是枚舉所有的x太浪費時間了。
改進的辦法是：用二分法在[max, sum]中間查找滿足條件的x，其中max是序列中最大元素，sum是所有元素的和。
3.1.2 通往奧格瑞瑪的道路
「通往奧格瑞瑪的道路」，來源：https://www.luogu.org/problem/P1462
∎題目描述
給定無向圖，n個點，m條雙向邊，每個點有點權fi（這個點的過路費），有邊權ci（這條路的血量）。求起點1到終點N的所有可能路徑中，在總邊權（總血量）不超過給定的b的前提下，所經過的路徑中最大點權（這條路徑上過路費最大的那個點）的最小值是多少。
題目數據：n≤10000，m≤50000，fi，ci，B≤1e9。
∎題解
對點權fi進行二分，用dijkstra求最短路，檢驗總邊權是否小於b。二分法是最小化最大值問題。
這一題是二分法和最短路算法的簡單結合。
（1）對點權（過路費）二分。題目的要求是：從1到N有很多路徑，其中的一個可行路徑Pi，它有一個點的過路費最大，記為Fi；在所有可行路徑中，找到那個有最小F的路徑，輸出F。解題方案是：先對所有點的fi排序，然後用二分法，找符合要求的最小的fi。二分次數log(fi)=log(1e9) < 30。
（2）在檢查某個fi時，刪除所有大於fi的點，在剩下的點中，求1到N的最短路，看總邊權是否小於b，如果滿足，這個fi是合適的（如果最短路的邊權都大於b，那麼其他路徑的總邊權就更大，肯定不符合要求）。一次Dijkstra求最短路，複雜度是O(mlogn)。
總複雜度滿足要求。
3.2 最小值最大化（最小值儘量大）
∎題目描述
「進擊的奶牛」，來源：https://www.luogu.org/problem/P1824
在一條很長的直線上，指定n個坐標點（x1, …, xn）。有c頭牛，安排每頭牛站在其中一個點（牛棚）上。這些牛喜歡打架，所以儘量距離遠一些。問最近的兩頭牛之間距離的最大值可以是多少。
這個題目裡，所有的牛棚兩兩之間的距離有個最小值，題目要求使得這個最小值最大化。
∎題解
（1）暴力法。從小到大枚舉最小距離的值dis，然後檢查，如果發現有一次不行，那麼上次枚舉的就是最大值。如何檢查呢？用貪心法：第一頭牛放在x1，第二頭牛放在xj≥x1+dis的點xi,第三頭牛放在xk≥xj+dis的點xk，等等，如果在當前最小距離下，不能放c條牛，那麼這個dis就不可取。複雜度O(nc)。
（2）二分。分析從小到大檢查dis的過程，發現可以用二分的方法找這個dis。這個dis符合二分法：它有上下邊界、它是單調遞增的。複雜度O(nlogn)。
#include<bits/stdc++.h>
using namespace std;
int n,c,x[100005];//牛棚數量，牛數量，牛棚坐標
bool check(int dis){ //當牛之間距離最小為dis時，檢查牛棚夠不夠
int cnt=1, place=0; //第1頭牛，放在第1個牛棚
for (int i = 1; i < n; ++i) //檢查後面每個牛棚
if (x[i] - x[place] >= dis){ //如果距離dis的位置有牛棚
cnt++; //又放了一頭牛
place = i; //更新上一頭牛的位置
}
if (cnt >= c) return true; //牛棚夠
else return false; //牛棚不夠
}
int main(){
scanf("%d%d",&n, &c);
for(int i=0;i<n;i++) scanf("%d",&x[i]);
sort(x,x+n); //對牛棚的坐標排序
int left=0, right=x[n-1]-x[0]; //R=1000000也行，因為是log(n)的，很快
//優化：把二分上限設置為1e9/c
int ans = 0;
while(left < right){
int mid = left + (right - left)/2; //二分
if(check(mid)){ //當牛之間距離最小為mid時，牛棚夠不夠?
ans = mid; //牛棚夠，先記錄mid
left = mid + 1; //擴大距離
}
else
right = mid; //牛棚不夠，縮小距離
}
cout << ans; //列印答案
return 0;
}
4. 實數二分
4.1 基本形式
實數域上的二分，比整數二分簡單。
實數二分的基本形式
const double eps =1e-7; //精度。如果下面用for，可以不要eps
while(right - left > eps){ //for(int i = 0; i<100; i++){
double mid = left+(right-left)/2;
if (check(mid)) right = mid; //判定，然後繼續二分
else left = mid;
}
其中，循環用2種方法都可以：
while(right - left > eps) { ... }
或者：
for(int i = 0; i < 100; i++) { ... }
如果用for循環，由於循環內用了二分，執行100次，相當於實現了 1/2100的精度，一般比eps更精確。
for循環的100次，比while的循環次數要多。如果時間要求不是太苛刻，用for循環更簡便[參考李煜東《算法競賽進階指南》27頁的說明]。
4.2 實數二分例題
∎題目描述
「Pie」，題目來源：http://poj.org/problem?id=3122
主人過生日，m個人來慶生，有n塊半徑不同的圓形蛋糕，由m+1個人（加上主人）分，每人的蛋糕必須一樣重，而且是一整塊（不能是幾個蛋糕碎塊，也就是說，每個人的蛋糕都是從一塊圓蛋糕中切下來的完整一塊）。問每個人能分到的最大蛋糕是多大。
∎題解
最小值最大化問題。設每人能分到的蛋糕大小是x，用二分法枚舉x。
「Pie」題的代碼
#include<stdio.h>
#include<math.h>
double PI = acos(-1.0); //3.141592653589793;
#define eps 1e-5
double area[10010];
int n,m;
bool check(double mid){
int sum = 0;
for(int i=0;i<n;i++) //把每個圓蛋糕都按大小mid分開。統計總數
sum += (int)(area[i] / mid);
if(sum >= m) return true; //最後看總數夠不夠m個
else return false;
}
int main(){
int T; scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m); m++;
double maxx = 0;
for(int i=0;i<n;i++){
int r; scanf("%d",&r);
area[i] = PI*r*r;
if(maxx < area[i]) maxx = area[i]; //最大的一塊蛋糕
}
double left = 0, right = maxx;
for(int i = 0; i<100; i++){
//while((right-left) > eps) { //for或者while都行
double mid = left+(right-left)/2;
if(check(mid)) left = mid; //每人能分到mid大小的蛋糕
else right = mid; //不夠分到mid大小的蛋糕
}
printf("%.4f\n",left); // 列印right也對
}
return 0;
}
5. 二分法習題
飢餓的奶牛 https://www.luogu.org/problem/P1868
尋找段落 https://www.luogu.org/problem/P1419
小車問題 https://www.luogu.org/problem/P1258
借教室 https://www.luogu.org/problem/P1083
跳石頭 https://www.luogu.org/problem/P2678
聰明的質監員 https://www.luogu.org/problem/P1314
分梨子 https://www.luogu.org/problem/P1493
第k大 http://acm.hdu.edu.cn/showproblem.php?pid=6231
6. 三分法求極值
6.1 原理
三分法求單峰（或者單谷）的極值，是二分法的一個簡單擴展。
單峰函數和單谷函數如下圖，函數f(x)在區間[l, r]內，只有一個極值v，在極值點兩邊，函數是單調變化的。以單峰函數為例，在v的左邊，函數是嚴格單調遞增的，在v右邊是嚴格單調遞減的。
下面的講解都以求單峰極值為例。
如何求單峰函數最大值的近似值？雖然不能直接用二分法，不過，只要稍微變形一下，就能用了。
在[l, r]上任取2個點，mid1和mid2，把函數分成三段。有以下情況：
（1）若f(mid1) < f(mid2)，極值點v一定在mid1的右側。此時，mid1和mid2要麼都在v的左側，要麼分別在v的兩側。如下圖所示。
下一步，令l = mid1，區間從[l, r]縮小為[mid1, r]，然後再繼續把它分成三段。
（2）同理，若f(mid1) > f(mid2)，極值點v一定在mid2的左側。如下圖所示。下一步，令 r = mid2，區間從[l, r]縮小為[l, mid2]。
不斷縮小區間，就能使得區間[l, r]不斷逼近v，從而得到近似值。
如何取mid1和mid2？有2種基本方法：
（1）三等分：mid1和mid2為[l, r]的三等分點。那麼區間每次可以減少三分之一。
（2）近似三等分：計算[l, r]中間點mid = (l + r) / 2，然讓mid1和mid2非常接近mid，例如mid1 = mid - eps，mid2 = mid + eps，其中eps是一個很小的值。那麼區間每次可以減少接近一半。
方法（2）比方法（1）要稍微快一點。
(有網友說不要用方法（2）：「因為在有些情況下這個 eps 過小可能導致這兩個算出來的相等，如果相等就有可能會判斷錯方向，所以其實不建議這麼寫，log3 和 log2 本質上是一樣的。」)
注意：單峰函數的左右兩邊要嚴格單調，否則，可能在一邊有f(mid1) == f(mid2)，導致無法判斷如何縮小區間。
6.2 實數三分
下面用一個模板題給出實數三分的兩種實現方法。
∎題目描述
「模板三分法」，來源：https://www.luogu.com.cn/problem/P3382
給出一個N次函數，保證在範圍[l, r]內存在一點x，使得[l, x]上單調增，[x, r]上單調減。試求出x的值。
∎題解
下面分別用前面提到的2種方法實現：（1）三等分；（2）近似三等分。
（1）三等分
mid1和mid2為[l, r]的三等分點
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
int n;
double a[15];
double f(double x){ //計算函數值
double s=0;
for(int i=n;i>=0;i--) //注意函數求值的寫法
s = s*x + a[i];
return s;
}
int main(){
double L,R;
scanf("%d%lf%lf",&n,&L,&R);
for(int i=n;i>=0;i--) scanf("%lf",&a[i]);
while(R-L > eps){ // for(int i = 0; i<100; i++){ //用for也行
double k =(R-L)/3.0;
double mid1 = L+k, mid2 = R-k;
if(f(mid1) > f(mid2))
R = mid2;
else L = mid1;
}
printf("%.5f\n",L);
return 0;
}
（2）近似三等分
mid1和mid2在[l, r]的中間點附近
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
int n; double a[15];
double f(double x){
double s=0;
for(int i=n;i>=0;i--) s=s*x+a[i];
return s;
}
int main(){
double L,R;
scanf("%d%lf%lf",&n,&L,&R);
for(int i=n;i>=0;i--) scanf("%lf",&a[i]);
while(R-L > eps){ // for(int i = 0; i<100; i++){ //用for也行
double mid = L+(R-L)/2;
if(f(mid - eps) > f(mid))
R = mid;
else L = mid;
}
printf("%.5f\n",L);
return 0;
}
6.2.1 實數三分習題
（1）「三分求極值」，題目來源：http://hihocoder.com/problemset/problem/1142
∎題目描述：在直角坐標系中有一條拋物線y = ax^2 + bx + c和一個點P(x, y)，求點P到拋物線的最短距離d。
∎題解：直接求距離很麻煩。觀察這一題的距離D，發現它滿足單谷函數的特徵，用三分法很合適。
（2）三分套三分，是計算幾何的常見題型。
「Line belt」，題目來源：http://acm.hdu.edu.cn/showproblem.php?pid=3400
∎題目描述：給定兩條線段AB、CD ，一個人在AB上跑的時候速度是p，在CD上速度是q，在其他地方跑速度是r。問從A點到D點最少的時間。
∎題解：從A出發，先走到AB上一點X，然後走到CD上一點Y，最後到D。時間是：
time = |AX|/p + |XY|/r + |YD|/q
假設已經確定了X，那麼目標就是在CD上找一點Y，使|XY|/r + |YD|/q最小，這是個單峰函數。三分套三分就可以了。
6.3 整數三分
整數三分的形式是：
while (left < right) {
int mid1 = left + (right - left)/3;
int mid2 = right- (right - left)/3;
if(check(mid1) > check(mid2))
… //移動right
else
… //移動left
}
下面是一個例題。
∎題目描述
「期末考試」，題目來源：https://www.lydsy.com/JudgeOnline/problem.php?id=4868
有n位同學，每位同學都參加了全部的m門課程的期末考試，都在焦急的等待成績的公布。第i位同學希望在第ti天或之前得知所有課程的成績。如果在第ti天，有至少一門課程的成績沒有公布，他就會等待最後公布成績的課程公布成績，每等待一天就會產生C不愉快度。對於第i門課程，按照原本的計劃，會在第bi天公布成績。有如下兩種操作可以調整公布成績的時間：1.將負責課程X的部分老師調整到課程Y，調整之後公布課程X成績的時間推遲一天，公布課程Y成績的時間提前一天；每次操作產生A不愉快度。2.增加一部分老師負責學科Z，這將導致學科Z的出成績時間提前一天；每次操作產生B不愉快度。上面兩種操作中的參數X,Y,Z均可任意指定，每種操作均可以執行多次，每次執行時都可以重新指定參數。現在希望你通過合理的操作，使得最後總的不愉快度之和最小，輸出最小的不愉快度之和即可。
∎題解
不愉快度是一個下凹的函數，用三分法。代碼略。
————————————————
版權聲明：本文為CSDN博主「羅勇軍」的原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處連結及本聲明。
原文連結：https://blog.csdn.net/weixin_43914593/article/details/103250854
京東活動中，機會難得！
本 書 介 紹
作者：羅勇軍、郭衛斌
定價：59.80元
ISBN：978730252915
120分鐘視頻講解！本書是算法競賽的入門和進階教材，包括算法思路、模板代碼、知識體系、賽事相關等內容。本書把競賽常用的知識點和競賽題結合起來，講解清晰、透徹，幫助初學者建立自信心，快速從實際問題入手，模仿經典代碼解決問題，進入中級學習階段。全書分為12章，覆蓋了目前算法競賽中的主要內容，包括算法競賽概述、算法複雜度、STL和基本數據結構、搜索技術、高級數據結構、基礎算法思想、動態規劃、數學、字符串、圖論、計算幾何。點擊查看本書的【教學大綱】
福 利
如果你在京東購買了本書，請將訂單和評價截圖發到郵箱itbook8@163.com
可以免費獲取額外贈送的ACM題庫。
視 頻 賞 析
讀 者 反 饋