二分的基础用法是在单调序列或单调函数中进行查找。因此当问题的答案具有单调性时，就可以通过二分把求解转化为判定。其实，写二分的时候并不容易，写check函数的时候，有很多细节之处需要仔细考虑。

  • 对于整数域上的二分，需要注意终止边界、左右区分取舍时的开闭请，避免漏掉进入死循环。
  • 对于实数域上的二分，需要注意精度问题。

二分的实现模板有很多种，以下给出的模板是yxc的，非常好用。

  1. //模板请记忆
  3. //整数二分
  4. bool check(int x) {/* ... */} // 检查x是否满足某种性质
  6. // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
  7. int bsearch_1(int l, int r)
  8. {
  9.     while (l < r)
  10.     {
  11.         int mid = l + r >> 1;
  12.         if (check(mid)) r = mid;    // check()判断mid是否满足性质
  13.         else l = mid + 1;
  14.     }
  15.     return l;
  16. }
  18. // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
  19. int bsearch_2(int l, int r)
  20. {
  21.     while (l < r)
  22.     {
  23.         int mid = l + r + 1 >> 1;
  24.         if (check(mid)) l = mid;
  25.         else r = mid - 1;
  26.     }
  27.     return l;
  28. }
  30. //注意，分析题意，画数轴，看mid的右边是答案，还是mid的左边是答案

upd20211115，对于二分模板的认识，我现在认为不应该局限于模板本身，下面的代码更好去理解，也很专业。在初赛真题当中，有很多次二分，具体代码实现的环节，就有两种

  1. while (l < r)
  3. while (l <= r)
  5. 这两种在当时判断边界是用填空去写的，比较容易进坑，需要代数模拟。现在这两种写法一起组合，对二分的理解用会深入很多。边界确实是一个头疼的话题，很容错，然后，很难调。
  7. 我现在更青睐后者
  1. // 数的范围
  2. // https://www.acwing.com/problem/content/description/791/
  4. #include <bits/stdc++.h>
  6. using namespace std;
  8. const int N = 1e5 + 10;
  10. int n, q, a[N], k;
  12. int solve(int k){
  13.     int l = 0, r = n - 1, best = -1;
  14.     while (l <= r){
  15.         int mid = (l + r) >> 1;
  16.         if (a[mid] <= k){
  17.             best = mid;
  18.             l = mid + 1;
  19.         }
  20.         else
  21.             r = mid - 1;
  22.     }
  24.     if (a[best] != k) return -1;
  25.     return best;
  26. }
  28. int solve2(int k){
  29.     int l = 0, r = n - 1, best = -1;
  30.     while (l <= r){
  31.         int mid = (l + r) >> 1;
  32.         if (a[mid] >= k){
  33.             best = mid;
  34.             r = mid - 1;
  35.         }
  36.         else
  37.             l = mid + 1;
  38.     }
  40.     if (a[best] != k) return  -1;
  41.     return best;
  42. }
  44. int main(){
  45.     cin >> n >> q;
  46.     for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  48.     while (q--){
  49.         scanf("%d", &k);
  51.         int l = solve2(k);
  52.         int r = solve(k);
  54.         printf("%d %d\n", l, r);
  55.     }
  57.     return 0;
  58. }
  1. //模板请记忆
  3. //浮点数二分，还有循环50次的写法
  4. bool check(double x) {/* ... */} // 检查x是否满足某种性质
  6. double bsearch_3(double l, double r)
  7. {
  8.     const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
  9.     while (r - l > eps)
  10.     {
  11.         double mid = (l + r) / 2;
  12.         if (check(mid)) r = mid;
  13.         else l = mid;
  14.     }
  15.     return l;
  16. }
  18. double bsearch_4(double l, double r)
  19. {
  20.     int T = 50;
  21.     while (T--)
  22.     {
  23.         double mid = (l + r) / 2;
  24.         if (check(mid)) r = mid;
  25.         else l = mid;
  26.     }
  27.     return l;
  28. }

例题，和为给定数

  1. //

例题，查找最接近的元素

  1. //