整数二分模板

在选用模板的时候要考虑下l=r-1的情况下mid是取l还是r，如果是r=mid则选mid = l+r >>1;否则l=mid选l+r+1>>1。

  1. bool check(int x) {/* ... */} // 检查x是否满足某种性质
  3. // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
  4. int bsearch_1(int l, int r)
  5. {
  6.     while (l < r)
  7.     {
  8.         int mid = l + r >> 1;
  9.         if (check(mid)) r = mid;    // check()判断mid是否满足性质
  10.         else l = mid + 1;
  11.     }
  12.     return l;
  13. }
  15. // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
  16. int bsearch_2(int l, int r)
  17. {
  18.     while (l < r)
  19.     {
  20.         int mid = l + r + 1 >> 1;
  21.         if (check(mid)) l = mid;//此时如果mid不加1的话在l=r-1的时候，mid=l，会进入死循环
  22.         else r = mid - 1;
  23.     }
  24.     return l;
  25. }

浮点数二分模板

不用+1和-1就不用处理边界

  1. bool check(double x) {/* ... */} // 检查x是否满足某种性质
  3. double bsearch_3(double l, double r)
  4. {
  5.     const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
  6.     while (r - l > eps)
  7.     {
  8.         double mid = (l + r) / 2;
  9.         if (check(mid)) r = mid;
  10.         else l = mid;
  11.     }
  12.     return l;
  13. }