如何查找第一个等于target的，最后一个等于target的，第一个大于等于target的，第一个小于等于target的。
第一种情况：首先是最基本的二分查找：
int bs1(vector<int> arr,int key){
int L = 0,R = arr.size() - 1; //在[L,R]范围内寻找key
int mid;
while( L <= R)//这里一定要写成小于等于，举个最简单的例子，｛1，3，4｝寻找4，如果缺少等于就找不到
{
mid = L + ((R - L) >> 1);
if(arr[mid] == key)
return mid;
if(arr[mid] > key)
R = mid - 1;// key 在 [L,mid-1]内
else
L = mid + 1;
}
return -1;
}
第二种情况：寻找第一个=key的，如果不存在返回-1
这个和之前的不同是:
数组中可能有重复的key，我们要找的是第一个key的位置；怎么寻找呢，第一种情况的目标是寻找到一个等于key的数就可以返回了，但是在这里，需要寻找的是第一个等于的数，所以就算当前的arr[mid]与key相等，依然还要往前寻找，所以就修改之前的arr[mid]>key修改为arr[mid]>=key，这样就算遇到了等于key的答案，依然不会返回，会继续往前寻找是否有其它等于key的值，最后跳出循环之后，如果L满足L < arr.size（） && arr[L] == key，返回L的值作为结果，否则输出-1，代表没有找到。下面就来通过三种情况具体分析这样是否可行。
1、找到一个等于key的数，并且它的前面没有等于key的数了。举个例子：1，2，3，5，6，6，6，6，6，6（key=6）.假设目前L指向0，R指向9，mid指向4，那么已经找到了key值，但是根据算法，R=mid-1，R等于3，然后继续进行循环，由于现在没有另外一个key了，所以最后一次循环输入必然是L=R=3，根据算法，会执行L=mid+1=4然后不满足情况输出，得到最终结果。
2、找到一个等于key的数，但是它的前面还有等于key的数。依然举例：1，2，3，5，6，6，6，6，6，6，6（key=6）.假设目前L指向0，R指向10，mid指向5，那么已经找到了key值，但是根据算法，R=mid-1，R等于4，和上面类似的原因最后依然可以得到正确答案。
3，假如数组中不存在KEY，那么输出条件的arr[L] == key就不会满足，输出的依然是-1；
总结来说就是这个算法保证了L只会指向第一个等于KEY的值，在KEY存在的情况下。
/**查找第一个与key相等的元素的下标， 如果不存在返回-1 */
int firstEqual(vector<int> arr,int key){
int L = 0, R = arr.size() - 1; //在[L,R]查找第一个>=key的
int mid;
while( L <= R){
mid = L + ((R - L) >> 1);
if(arr[mid] >= key)
R = mid - 1;
else
L = mid + 1;
}
if(L < arr.size() && arr[L] == key)
return L;
return -1;
}
第三种情况：寻找最后一个=key的，如果不存在返回-1
和上面情况一样，只是反过来就OK了，同理就是保证R只会指向最后一个存在的KEY，否则就是不存在。
/**查找第一个大于等于key的元素的下标*/
int lasteuual(vector<int> arr,int key){
int L = 0, R = arr.size() - 1;
int mid;
while( L <= R){
mid = L + ((R - L) >> 1);
if(arr[mid] <= key)
L = mid + 1;
else
R = mid - 1;
}
if(R >= 0 && arr[R] == key)
return R;
return -1;
}
第四种情况：第一个>=key的，
和第二种情况有点类似，很简单，第二种情况是寻找第一个==KEY的数，如果没有就返回-1，直接去掉最后的判断，因为如果没有等于key的数，那么就直接返回L就可以了，L有几种情况，第一个是L没有超过上限，那么返回的就是正确的结果，如果L=arr.size()，那么说明整个数组都小于key，直接返回-1；原理是怎么样的呢，如果数组中有key的情况下，那么最后按照第二种情况的思想，会返回正确的答案，主要讨论的是没有key的情况，依然是分为三种情况：
1、所有元素大于key，那么L肯定是不会变化的，因为不会运行到L=mid+1这一条分支，最后返回0，答案正确
2、所有元素小于key，那么R肯定是不会变化的，因为不会运行到R=mid-1，那么最后一次循环肯定就是当l=r的时候，依然还是走了L=mid+1着一个分支，因为R是不会变换的，R最开始是arr.size()-1,加一之后肯定返回arr.size().答案正确
3、不存在key，但是数组元素有比key大的，有比key小的，这种情况下，R可能有两种指向，指向最后一个小于key的数，指向第一个大于key的数，不可能再往前或者往后指了，但是最后的跳出循环的条件必然是L=R，那么如果指向小于key的数，跳出循环钱做L+1，或者指向大于key，跳出循环前做R-1，结果都是正确的。
int firstlargeEqual(vector<int> arr,int key){
int L = 0, R = arr.size() - 1; //在[L,R]查找第一个>=key的
int mid;
while( L <= R){
mid = L + ((R - L) >> 1);
if(arr[mid] >= key)
R = mid - 1;
else
L = mid + 1;
}
if(L < arr.size())
return L;
return -1;
}
第五种情况：最后一个<=key的
分析情况和上面是一样的。
static int lastSmallEqual(vector<int> arr,int key){
int L = 0, R = arr.size() - 1;
int mid;
while( L <= R){
mid = L + ((R - L) >> 1);
if(arr[mid] <= key)
L = mid + 1;
else
R = mid - 1;
}
return R;
}
第六种情况：第一个>key的
这个和第二种和第四种的不同在于:if(arr[mid] >= key) 改成了 if(arr[mid] > key)，因为不是要寻找 = key的；而是要寻找>key的，但是因为是寻找第一个大于的，所以依然找到后不能直接返回，和普通的二分法有点像，但是没有==key跳出，最后依然是返回L。依然是分三种情况：
1、全部小于key，那么R不会变，直到最后都不会变，所以返回的L=mid+1=R+1=arr.size()-1+1=arr.size()
2、全部大于key，那么L不会变，最后返回L，L=0
3、有大于的，有小于的，那么一样的道理，因为等于key的时候是选择做L=mid-1，所以R最小只能指向最后一个等于key或者最后一个小于key的值（无key的情况下），那么最后的结果是返回L=R+1，依然是返回了第一个大于key的数。
/**查找第一个大于key的元素的下标 */
static int firstLarge(vector<int> arr,int key){
int L = 0,R = arr.size() - 1;
int mid;
while(L <= R){
mid = L + ((R - L) >> 1);
if(arr[mid] > key)
R = mid - 1;
else
L = mid + 1;
}
return L;
}
第七种情况：最后一个<key 的
道理和上面是一样的，就不多说了。
static int lastSmall(vector<int> arr,int key){
int L = 0, R = arr.size() - 1;
int mid;
while(L <= R){
mid = L + ((R - L) >> 1);
if(arr[mid] < key)
L = mid + 1;
else
R = mid - 1;
}
return R;
}
通过对上面其中情况进行分析，可以很明显的看出，第一个……的情况一般都是返回L，最后一个……的情况一般都是返回R。