二分模板一共有兩個，分別適用于不同情況。
算法思路：假設目標值在閉區間[l, r]中， 每次將區間長度縮小一半，當l = r時，我們就找到了目標值。
版本一
當我們將區間[l, r]劃分成[l, mid]和[mid + 1, r]時，其更新操作是r = mid或者l = mid + 1;計算mid時不需要加1。
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;
}
版本二
當我們將區間[l, r]劃分成[l, mid - 1]和[mid, r]時，其更新操作是r = mid - 1或者l = mid;此時為了防止死循環，計算mid時需要加1。
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}return l;
}
總結
假設有一個總區間，經由我們的 check 函數判斷后，可分成兩部分，
這邊以o作 true，…作 false 示意較好識別
如果我們的目標是下面這個v，那麼就必須使用模板 1
…vooooooooo
假設經由 check 劃分后，整個區間的屬性與目標v如下，則我們必須使用模板 2
oooooooov…
所以下次可以觀察 check 屬性再與模板1 or 2 互相搭配就不會寫錯啦
練習題
503. 借教室
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;
const int N = 1000010;
int n, m;
int w[N];
int d[N], l[N], r[N];
LL b[N];bool check(int mid)
{memset(b, 0, sizeof b);for (int i = 1; i <= mid; i ++ ) {b[l[i]] += d[i];b[r[i] + 1] -= d[i];}for (int i = 1; i <= n; i ++ ) {b[i] += b[i - 1];if (b[i] > w[i]) return false;}return true;
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);for (int i = 1; i <= m; i ++ ) scanf("%d%d%d", &d[i], &l[i], &r[i]);int l = 0, r = m;while(l < r){int mid = l + r + 1>> 1;if (check(mid)) l = mid;else r = mid - 1;}if (r == m) printf("0\n");else printf("-1\n%d", r + 1);return 0;
}作者：大四萌新.
鏈接：https://www.acwing.com/activity/content/code/content/7899026/
來源：AcWing
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
1227. 分巧克力
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1e5 + 10;int n, k;
int h[N], w[N];bool check(int mid)
{int sum = 0;for (int i = 0; i < n; i ++ ) {sum += (h[i] / mid) * (w[i] / mid);if (sum >= k) return true;}return false;
}int bsearch()
{int l = 1, r = 1e5 + 10;while (l < r) {int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}
}int main()
{scanf("%d%d", &n, &k);for (int i = 0; i < n; i ++ ) scanf("%d%d", &h[i], &w[i]);printf("%d", bsearch());return 0;
}作者：大四萌新.
鏈接：https://www.acwing.com/activity/content/code/content/7878482/
來源：AcWing
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
4956. 冶煉金屬
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 10010;
int n;
int a[N], b[N];bool check_1(int mid)
{// 找最小的 那么其他部分都得滿足小于等于b[i]for (int i = 0; i < n; i ++ ) if (a[i] / mid > b[i]) return false;return true;
}bool check_2(int mid)
{// 找最大得 那么其他部分都得滿足大于等于b[i]for (int i = 0; i < n; i ++ ) if (a[i] / mid < b[i]) return false;return true;
}int main()
{scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d%d", &a[i], &b[i]);int l = 1, r = 1e9 + 1;while (l < r) {int mid = l + r >> 1;if (check_1(mid)) r = mid;else l = mid + 1;}printf("%d ", l);r = 1e9 + 1;while (l < r){int mid = l + r + 1 >> 1;if (check_2(mid)) l = mid;else r = mid - 1;}printf("%d", l);return 0;
}作者：大四萌新.
鏈接：https://www.acwing.com/activity/content/code/content/7899986/
來源：AcWing
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
)
