算法札记：二分

二分的本质不是单调性

二分的本质是序列二分后两段性质不同

比如对于这个数列：4 3 2 1 5 5 9 8 7 6（5左边的数小于等于5，5右边的数大于等于5）

我要找5第一次出现的位置，一样的可以用二分

为什么

我只需要执行这个任务：将序列划成两段，左段都小于5，右段都大于等于5，取右端第一个点

每次二分，我只需要执行这个判断：当前数(a[mid])大于等于5 吗？如果是，那他和他右边的数一定满足大于等于5，此时我想要的肯定在l~mid，缩右边界r=mid，反之缩左边界l=mid+1

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

若找5最后一次出现的位置，以此类推，懒得打字了

while (l<r){
int mid=l+r+1>>1;//???
if (a[mid]<=k){
l=mid;
}else{
r=mid-1;
}
}

//???+1的原因：如果不加一，带数据1 2，我找2，直接死循环