前言
在这篇文章中，我们将会一起学习二分算法，比上一章的滑动窗口要难上许多（对我来说）。
话不多说，我们直接开始。
1.二分算法的基本定义
一句话概括本质：通过判断左右边界所围成区域的中点的值和目标值的关系，来决定下一步要在该区域的哪半边继续进行同样的操作，直到触发循环的退出条件。
讲一讲流程就是(以左右闭区间为例)：假设我们拿到一个升序的序列nums和要查找的目标值target，那么我们开局将左边界left和右边界right都设立在这个序列的两头(举个例子，0和len(nums)-1)，进入循环后先取它的中点mid，判断nums[mid]的值：
如果nums[mid]≥target，那就选择左半边进行下一步，使right=mid-1；反之，选择右半边进行下一步，使left=mid+1。
周而复始，直到触发循环的退出条件(此处是left>right退出)。
2.如何进一步理解二分算法-红蓝染色法
可以先去看这个视频：【算法入门】用红蓝染色法学爆二分查找
在红蓝染色法中，我们将一个升序数组分成蓝区(<目标值的区域)，空白区和红区(>=目标值的区域)。我们二分就是把对应的元素染色到对应的区域。
在这个视频中，博主介绍了三种二分类型，分别是左右开区间、左右闭区间以及左闭右开区间。为了方便，本文章统一使用左右闭区间，即[l,r]。
在这个视频中，左右闭区间类型的二分算法在循环结束后，有一件事情是永远不变的，无论红蓝区的标准如何调整：l在红区的最左边，r在蓝区的最右边。如下图所示：
并且，按照我上面的分区设定，l会正好指在target上面(如果有)，如果没有target，会指在大于它的第一个数上面。所以如果你要找target或者大于它的第一个数，直接输出nums[l]就行了。
那么遇到其他类型又怎么办呢？假设题目就是想让我找>target的第一个数，并且nums中有可能本身就有target，如果还是按照上面的标准划定红蓝区，那么就有可能直接输出target了，这咋整呢？
先记住上面永远不变的事情，然后我们再去调整蓝区和红区的标准，就能做到这件事：把红区调整成>target的数全都在这里面，把蓝区调整成≤target的数全都在这里面。再看看上面永远不变的事情，是不是l自然而然就指到了比target大的第一个数上，并且即使有target，也不会指到target上。
那么反映到代码上，又会变成咋样呢？
先看看最上面情况的代码(蓝区是<目标值的区域，红区是>=目标值的区域)：
int lower_bound(vector<int>& nums,int target){
int l=0,r=nums.size()-1;
while (l<=r){
int mid=(l+r)/2;
//下面这一行代码是最关键的，是决定红蓝区域性质的核心代码
if (nums[mid]<target){ //由于l左边(不包含它自己)是蓝区，如果nums[mid]<target，
l=mid+1; //那么将其收入蓝区；
}else{ //如果nums[mid]≥target，
r=mid-1; //将其收入红区
}
}
return l;//输出红区的最左边的元素
}结合注释看，你现在一定有所体会了吧？所以，如果我们要求大于target的第一个数，那就按照上面的标准来更改红蓝区：把红区调整成>target的数全都在这里面，把蓝区调整成≤target的数全都在这里面。
int lower_bound(vector<int>& nums,int target){
int l=0,r=nums.size()-1;
while (l<=r){
int mid=(l+r)/2;
if (nums[mid]<=target){ //由于l左边(不包含它自己)是蓝区，如果nums[mid]<=target，
l=mid+1; //那么将其收入蓝区；
}else{ //如果nums[mid]>target，
r=mid-1; //将其收入红区
}
}
return l;//输出红区的最左边的元素
}这样一讲，是不是小于target的第一个数等等情况，你也能解决了？
如果要找小于target的第一个数，就直接将蓝区改成<target，红区改成≥target，最后l-1就是答案的位置(如果算出来是-1，说明不存在，target就是最小的数)。
其他情况就不讲了，举一反三即可。
