不是什么牛逼的二分，就是普通的二分
谁知道我都学到了这种程度，还能连二分都不会。。。
难绷啊
1.在一个序列里面二分查找第一个大于x的数字
// 在[i+1, n-1]的范围内查找第一个大于x的数的位置
int bingarySearch(int i, long long x){
if(a[n-1] <= x) return n; //都不大于x，返回n
int l = i + 1，r = n - 1;
while (l<r)
{
mid = (l+r)/2;
// 若a[mid]<=x, 说明第一个大于x的数只可能在mid后面
if(a[mid]<=x){
l = mid + 1;
}else{// 若大于，说明在mid之前（包含mid)
r = mid;
}
}
return l;
}
//摘自https://blog.csdn.net/Cainell/article/details/122485622，感谢大佬!
2.在一个序列里面二分查找第一个大于等于x的数字
// 在[i+1, n-1]的范围内查找第一个大于x的数的位置
int bingarySearch(int i, long long x){
if(a[n-1] <= x) return n; //都不大于x，返回n
int l = i + 1，r = n - 1;
while (l<r)
{
mid = (l+r)/2;
// 若a[mid]<=x, 说明第一个大于x的数只可能在mid后面
if(a[mid]<x){
l = mid + 1;
}else{// 若大于，说明在mid之前（包含mid)
r = mid;
}
}
return l;
}
//摘自https://blog.csdn.net/Cainell/article/details/122485622，感谢大佬
3.查找最后一个小于等于的数字
int l=0,r=max; while (l < r) { //取高位，取地位会遇见死循环 int mid=(l+r+1)/2; if(k>=dp[mid])l=mid; else r=mid-1; } return l;
4.查找最后一个小于的数字
int l=0,r=max; while (l < r) { //取高位，取地位会遇见死循环 int mid=(l+r+1)/2; if(k>dp[mid])l=mid; else r=mid-1; }
return l;
我的选择是，背下来
草