进一步探讨二分
二分看似简单,但需注意细枝末节
接下来简单探讨几种查询
以严格大于x的第一位数为例子
//序列为m ,x为查询的数
int find(int x){//假设序列长为n;
int l=1,r=n;
while(l<=r){
int mid=(l+r)>>1;
if(m[mid]<=x) l=mid+1;
else r=mid-1;
}//最后出现一定会出现 l==r,此时mid==l
// 若m[mid]<=x,则m[mid+1]>x;
//若m[mid]>x,则 m[l]>x,m[mid-1]<x
return m[l];
}
严格大于等于x的情况,只需要去掉等号号即可
严格小于x的情况,将小于符号改为大于符号即可
严格小于等于x的情况,也只需要去掉等号即可
写题过程中还有具体的探讨,可以从这几种方法中迁移应用