⭐寫在前面的話：本系列文章旨在複習算法刷題中常用的基礎算法與資料結構，配以詳細的圖例解釋，總結相應的代碼模闆，同時結合例題以達到最佳的學習效果。本專欄面向算法零基礎但有一定的C++基礎的學習者。若C++基礎不牢固，可參考：10min快速回顧C++文法，進行文法複習。
🔥本文已收錄于算法基礎系列專欄： 算法基礎教程 免費訂閱，持續更新。
二分
整數二分
如果有單調性，就一定可以二分。但是有二分的不一定非得有單調性。
二分的本質是邊界，将區間分為兩個，一邊滿足某條性質，另一邊不滿足某條性質。然後可以找到這兩個區間的邊界，找任意一個區間的邊界都可以。
但是找紅色邊界和綠色邊界略有差別：
紅色邊界：
細節：關于為什麼mid = (l + r +1) / 2 ，因為C++中取整是下取整。
- 假設mid = (l + r ) / 2 ；如果是 l = r - 1;那麼下取整後 mid = l ，會陷入死循環。
也可以找綠色邊界：
例題：數的範圍
給定一個按照升序排列的長度為 n 的整數數組，以及 q 個查詢。
對于每個查詢，傳回一個元素 k 的起始位置和終止位置（位置從 00 開始計數）。
如果數組中不存在該元素，則傳回
-1 -1
。
輸入格式
第一行包含整數 n 和 q，表示數組長度和詢問個數。
第二行包含 n 個整數（均在 1∼10000 範圍内），表示完整數組。
接下來 q 行，每行包含一個整數 k，表示一個詢問元素。
輸出格式
共 qq 行，每行包含兩個整數，表示所求元素的起始位置和終止位置。
如果數組中不存在該元素，則傳回
-1 -1
。
資料範圍
1≤n≤100000
1≤q≤10000
1≤k≤10000
輸入樣例：
6 3
1 2 2 3 3 4
3
4
5 輸出樣例：
3 4
5 5
-1 -1 代碼模闆
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int m ,n ;
int q[N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n ; i++)scanf("%d",&q[i]);
while( m --)
{
int x;
scanf("%d", &x);
int l = 0 , r = n - 1;
while( l < r)
{
int mid = l + r >> 1;
if(q[mid] >= x)r = mid;
else l = mid + 1;
}
//上面二分出來的是第一個滿足大于等于x的數，如果沒有x，則是大于x的數。
if(q[l] != x)cout << "-1 -1" <<endl;
//對該數進行判斷，如果不滿足，則傳回-1-1。
else
{
//找到最後一個x的位置
cout << l << ' ';
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] <= x)l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}
} 浮點數二分
浮點數二分思路同上，有個好處是不需要處理邊界。
例題：開平方
給定一個浮點數 n，求它的三次方根。
輸入格式
共一行，包含一個浮點數 n。
輸出格式
共一行，包含一個浮點數，表示問題的解。
注意，結果保留 6 位小數。
資料範圍
−10000≤n≤10000
輸入樣例：
4 輸出樣例：
2.000000 代碼模闆
#include<bits/stdc++.h>
using namespace std;
int main()
{
double x;
cin >> x;
double l = 0, r =x ;
while(r - l > 1e-8)
{
double mid = (l + r)/2;
if(mid * mid >= x)r = mid;
else l = mid ;
}
printf("%lf", l);
return 0;
} 這裡要強調的是精度問題：
while(r - l > 1e-8) 誤差過大會導緻精度不足。
這裡給出一些經驗值：誤內插補點一般比保留位數多2
| 保留位數 | 誤內插補點 |
| 4 | 1e-6 |
| 5 | 1e-7 |
| 6 | 1e-8 |
當然可以采用其他寫法：
for(int i = 0; i < 100 ; i++);