二分分为两大块：

1. 整数二分（蛋疼）
2. 浮点数二分

以后用$q$代替一个有序数组（有单调性的数组一定可以二分）

整数二分

整数二分的本质是边界。

思想：

大体思路：定义一种性质$check$，把$q$分成两部分（两部分没有交点），左半边不满足性质，右半边满足性质，可以求出性质的边界，两种情况。

第一种：要求的是左半边的边界

第一步：定义中间点$mid=(l+r+1)/2$，判断它满不满足$cheak$

1. 满足。边界在$[l, mid-1], r=mid-1$。
2. 不满足。边界在$[mid, r], l=mid$;

第二步：重复第一步，直到$l=r$，$q_l$（或$q_r$）就是答案。

第二种：要求的是右半边的边界

第一步：定义中间点$mid=(l+r)/2$，判断它满不满足$cheak$

1. 满足。边界在$[l, mid], r=mid$。
2. 不满足。边界在$[mid+1, r], l=mid+1$;

第二步与第一种情况一样。

一个问题：为什么第一种情况的$mid$还要$+1$。

答：如果没有$+1$，当$l=r-1$的时候，如果$check$成功了，$l=mid=l$，就陷入死循环了。

模版：

bool check(int mid){
    按情况而定;
}

情况一：

int bsearch(int l, int r){
    while (l < r){
        int mid = l + r + 1 >> 1;
        if (cheak(mid)) r = mid - 1;
        else l = mid;
    }
    return l;
}

情况二：

int bsearch(int l, int r){
    while (l < r){
        int mid = l + r >> 1;
        if (cheak(mid)) r = mid;
        else l = mid + 1;
    }
}

浮点数二分

本质也是边界（没整数二分那么蛋疼）

思路：

大体思路：跟整数二分差不多，只是浮点数没有整除，所以每次都能严格分成两半

第一步：定义中间点$mid=(l+r)/2$，判断他满不满足$check$

1. 满足。答案在$[l, mid]$中，$r=mid$。
2. 不满足。答案在$[mid, r]$中，$l=mid$。

第二步：重复第一步，直到$l$和$r$相差非常小，精度足够了的时候，可以输出$l$或$r$。

模版：

先定义$check$

int bsearch(double l, double r){
    while (r - l < 精度){
        double mid = l + r >> 1;
        if (check(mid)) l = mid;
        else r = mid;
    }
    return l;
}