整数二分

1. 二分的本质并不是单调性，有单调可以用二分，用二分不一定得是单调；
2. 二分的本质是条件和边界；
3. 关于要不要加1，就看是l=mid还是r=mid； ```cpp bool check(int x) {/ … /} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; } return l; } // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用： 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; }

<a name="VrBN2"></a>
# 浮点数二分
**注意**
1. eps的值要比题目中的小数位多2位
1. 要注意边界和范围，比如0.01的三次方根
可以让l=-10000和r=10000<br />或者分正负两种情况，让一个的边界去max（1.0，n）或者max（-1.0，n）
```cpp
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}