二分法用于解决这样一类问题：一个区间能分成左右两部分，左半部分满足性质$A$，右半部分不满足性质$A$。问题的目标是求解这两部分的分界点。

所以二分法和区间里有没有单调性其实没什么关系，但是很多问题里是从单调性导出了上面的性质，上面的性质才是一个问题能用二分法求解的最本质的性质。

二分法每次取区间的中间元素，通过判断区间中点元素a[mid]是否满足性质$A$就能断定求解目标是在mid的左边还是右边，从而每次把求解区间长度缩减一半。

1 整数二分

1.1 特点

在整数二分问题里，需要考虑缩减区间时是否要保留mid这个点，也就是说mid是否可能作为解存在。

对于整数二分而言，“求分界点”也就是求左侧部分（满足性质$A$）的最后一个数，或者求右侧部分（不满足性质$A$）的第一个数。

二分过程结束后，l或者r（用哪个都行，因为最后它俩是相等的）的位置就是所求的位置。

1.2 求左侧部分（满足性质$A$）的最后一个数

由于是求左半部分的最后一个数，所以如果区间中点的数a[mid]是满足性质$A$的，那么a[mid]这个数就是左侧部分的数，它就有可能是“左侧部分的最后一个数”，因此这时候要把区间缩减成包括mid在内的右半部分，也就是从$[l,r]$变成$[mid,r]$，因此执行l = mid。

如果区间中点的数a[mid]是不满足性质$A$的，那么a[mid]这个数就是右侧部分的数，所以下一次要把区间从$[l,r]$变成$[l,mid-1]$，因此执行r = mid - 1。

在这类问题下，由于涉及l = mid这个操作，所以“计算区间中点mid”的这个操作要使用mid = (l + r + 1) / 2来计算。而不能使用mid = (l + r) / 2来计算，当l的值是r - 1的时候，mid = (l + r) / 2计算出来的的值是l，如果执行了l = mid的操作，那么区间是没有变化的，会陷入死循环。

这是因为除法会自动做下取整，然而计算mid的方法在这类问题里需要是：
$$mid=\lceil \frac{l+r}{2}\rceil$$

所以才要用mid = (l + r + 1) / 2来计算上取整后的值。

1.3 求右侧部分（不满足性质$A$）的第一个数

由于求的是右侧部分的第一个数，所以如果区间中点的数a[mid]是满足性质$A$的，那么a[mid]这个数就是左侧部分的数，所以下一次要把区间$[l,r]$变成$[mid+1,r]$，因此执行l = mid + 1。

如果区间中点的数a[mid]是不满足性质$A$的，那么a[mid]这个数就是右侧部分的数，它就有可能是”右侧部分的第一个数“，因此这时候要把区间缩减成包括mid在内的左半部分，也就是从$[l,r]$变成$[l,mid]$，因此执行$r=mid$。

在这类问题下，由于涉及r = mid这个操作，所以“计算区间中点mid”的这个操作要用mid = (l + r) / 2来计算。

这是因为除法会自动做下取整，计算mid的方法在这类问题里也正好是：
$$mid=\lfloor \frac{l+r}{2}\rfloor$$

所以才要用mid = (l + r) / 2来计算下取整后的值。

1.4 例题：数的范围

其实就是用两次二分法，分别求一下：

1. $>=x$的第一个数（把区间分成$<x$的左侧部分和$>=x$的右侧部分）
2. $<=x$的最后一个数（把区间分成$<=x$的左侧部分和$>x$的右侧部分）

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N];

int main() {
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    // 读入n个数
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    // 对于q次查询
    while (q -- ) {
        int x;
        cin >> x;
        // 要找第一个x，也就是>=x的第一个数
        // 二分法将其分成>=x的右半部分和<x的左半部分，找右半部分的第一个数
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        // 如果最后找到的位置不是x，说明x在数组中不存在
        if (a[l] != x) {
            cout << "-1 -1" << endl;
            continue;
        }
        cout << l << ' ';
        // 要找最后一个x，也就是<=x的最后一个数
        // 二分法将其分成<=x的左半部分和>x的右半部分，找左半部分的最后一个数
        l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (a[mid] <= x) l = mid;
            else r = mid - 1;
        }
        cout << l << endl;
    }
    
    return 0;
}

2 浮点数二分

2.1 特点

对于浮点数二分而言，“求分界点” 也就是找一个能够满足精度要求的解就可以了，不像整数二分那样有那么多的边界问题。

浮点数二分先根据数据的范围来确定二分答案的区间的范围$[l,r]$，浮点数二分就是对求解答案来二分，所以区间长度r - l就约束了答案的精度。

2.2 例题：数的三次方根

可以对答案（三次方根结果）进行二分求解，把区间分成左侧（三次方结果$<x$）和右侧（三次方结果$>x$）。所以只要mid * mid * mid > x，就把区间变成$[l,mid]$，只要mid * mid * mid < x就把区间变成$[mid,r]$。

浮点数不用考虑比较相等的情况了，所以可以直接把区间分成$<x$和$>=x$两侧，或者分成$<=x$和$>x$两侧就能求方便求解。

#include <iostream>

using namespace std;

int main() {
    // 由于要做浮点数比较，这里读入就直接读double
    double x;
    cin >> x;
    // 区间两个端点，这里确保l * l * l < x < r * r * r
    double l = -100, r = 100;
    // 精度1e-8
    while (r - l > 1e-8) {
        double mid = (l + r) / 2;
        if (mid * mid * mid > x) r = mid;
        else l = mid;
    }
    // 输出时注意精度要求
    printf("%.6lf\n", l);
    return 0;
}