AcWing算法基础1.3

二分

二分分为整数二分和实数二分，其中整数二分模板有两个

模板：

整数二分模板

第一种模板将区间分为[ l , mid ] 和 [ mid + 1, r ]

 1 int bsearch_1(int l, int r)
 2 {
 3     while(l < r)
 4     {
 5         int mid = l + r >> 1;
 6         if(check(mid))  r = mid;  // check为判断 mid 性质
 7         l = mid + 1;
 8     }
 9     return l;
10 }

第二种模板把区间分为[ l , mid - 1] 和 [ mid , r ]，需要注意的是，这里算mid时要用 l + r + 1 >> 1; 这里需要加一

 1 int bsearch_2(int l, int r)
 2 {
 3     while(l < r)
 4     {
 5         int mid = l + r + 1>> 1;
 6         if(check(mid))  l = mid; // check判断 mid 的性质
 7         r = mid - 1;
 8     }
 9     return l;
10 }，

计算 mid 时 +1，是因为防止陷入死循环，用第二种模板会有种情况使循环陷入死循环，例如某次更新后区间变成 [x1, x2 ] ，如果我们计算 mid 时不 +1，l + r >> 1为向下取整，所以我们计算的 mid 始终是 l ，此时 l < r 恒成立如果 if () 条件成立 l = mid，至此循环将一直进行下去，陷入死循环

实数二分就简单多了，因为我们不用考虑边界情况，直接二分即可

 1 double bsearch_3(double l, double r)
 2 {
 3     const double eps = 1e-6; //eps表示精度,取决于题目对精度的要求
 4     while(r - l > eps)
 5     {
 6         double mid = (l + r) / 2;
 7         if(check(mid))  r = mid;
 8         else l = mid;
 9     }
10     return l;
11 }