二分查找

版本1

　　当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

　　C++ 代码模板：

 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;
 7         else l = mid + 1;
 8     }
 9     return l;
10 }

版本2

　　当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

　　C++ 代码模板：

 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;
 7         else r = mid - 1;
 8     }
 9     return l;
10 }

浮点数二分

　　用mid去界定l 和 r 时不需要加减1

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 double a;
 7 
 8 double f(double m){
 9     if(m < 0)m = 0 - m;
10     //浮点数二分l 和 r 不需要加减一
11     double l = 0, r = 1000;
12     //这里的意思就是精确到小数点后6位
13     while(r - l > 1e-7){
14         double mid = (l + r) / 2;
15         if(mid*mid*mid < m)l = mid;
16         else r = mid;
17     }
18     
19     return r;
20 }
21 
22 int main(){
23     cin >> a;
24     if(a < 0)
25         printf("-%f",f(a));
26     else
27         printf("%f",f(a));
28     return 0;
29 }

作者：yxc
链接：https://www.acwing.com/blog/content/31/
来源：AcWing