二分：

1、常用写法：

c++ : STL

lower_bound(a.begin(), a.end(), x) - a.begin();
对应的是 第一个 >=x 的下标 
upper_bound(a.begin(), a.end(), x) - a.begin();
对应的是 第一个 > x 的下标 

拓展运用： 找第一个小于x的值的下标

int pos = lower_bound(a.begin(), a.end(), x) - a.begin() - 1;
!!!

2、!!!二分答案（二分运用）

特点 ：

1、答案在一个区间内， 区间很长， 暴力找会超时

2、答案满足二分性

3、求的答案是最值

4、通常表现为判断一个值是否符合要求很简单

常用写法（我的）

int l = ~, r = ~;
while(l <= r) {
   int mid = l + r >> 1;
   if(check(mid)) l = mid + 1; || r = mid - 1;
   else r = mid - 1; || l = mid + 1;
 }

反正记好了我这种写法， 最后 r 在左边， l 在右边

利用这个性质 + check 函数 推出我们需要的是 r 还是 l

细节！！！！

1、二分答案的最大特征为 ： 最小值中最大， 最大值中最小

2、注意边界值， 就是 l 和 r 的最初取值！！！

常常会在这里设坑

3、以后遇到最值问题：

（1）贪心 （2）二分 （3）动态规划