有序数列二分边界个人总结

一. x在数列取值范围内

1. 更新时r = mid不能让mid取到r，[l , mid] [mid + 1 , r]要不然会死循环，所以mid = l + r >> 1

r岿然不动每次更新成mid，而l每次日拱一卒更新成mid + 1，

循环停止时l == r，循环停止后的q[l],q[r]相等，一定满足对方的取值范围，即两者的取值范围取交集（l和r就是这么更新来的，不满足不更新）

A
大于x的第一个数, upper_bound

while (l < r)
{
    int mid = l + r >> 1;
    if (q[mid] > x) r = mid;    
    if (q[mid] <= x) l = mid + 1;
}

每次判断q[mid] > x才去更新r，r = mid，更新后的q[r] = q[mid]，更新后q[r] 取值范围为大于x

每次判断q[mid] <= x才去更新l，l = mid + 1，q[mid]最大取到x，更新后q[l]也就是q[mid + 1]最大取到大于x的第一个数，更新后q[l]取值范围为小于等于（大于x的第一个数）

循环终止，l == r，此时q[l] q[r]相等，肯定满足双方的取值范围，两者的的交集也就是大于x的第一个数

建议记忆成：更新成mid的那个条件并且靠近不等号最近的数

if (q[mid] >(=) x) r = mid;大于或大于等于x的第一个数

if (q[mid] <(=) x) l = mid;小于或小于等x的最靠后一个数

x = 3

B
大于等于x的第一个数，lower_bound

while (l < r)
{
    int mid = l + r >> 1;
    if (q[mid] >= x) r = mid;    
    else l = mid + 1;
}

2. 更新时l = mid不能让mid取到l，[l, mid - 1], [mid, r],要不然会死循环，所以mid = l + r + 1 >> 1

C
小于x的最靠后一个数

while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (q[mid] < x) l = mid;
    else r = mid - 1;
}

D
小于等于x的最靠后一个数

while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (q[mid] <= x) l = mid;
    else r = mid - 1;
} 

二. x在数列外部

X = 1 X = 10

开头补一个数，或者末尾补一个数，算是一个小技巧吧，回顾这题两种二分有感
AcWing 896. 最长上升子序列 II

与题无关
这里的l，r为数列初始左右端点
AB两种 mid 取不到r，只会根据r - 1来判定去不去r，并不在乎q[r]的值
CD两种 mid 取不到l，只会根据l + 1来判定去不去l，并不在乎q[l]的值

浮点数二分

只做过这题 680. 剪绳子
利用二分求近似解，不断逼近真实解，直到满足精度

对于区间[a，b]上连续不断且f（a）·f（b）<0的函数y=f（x），通过不断地把函数f（x）的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法

三分

        while (l < r - 1)
        {
            int mid = l + r >> 1;
            int rmid = mid + r >> 1;
            LL ll = find(mid);
            LL rr = find(rmid);
            if (ll > rr) l = mid;
            else r = rmid;
        }
        return min(find(r), find(l));

        while (l + eps < r)
        {
            int lmid = l + (r - l) / 3；
            int rmid = r - (r - l) / 3;
        }