先上模板:
bool check(int x) {} // 检查x是否满足某种性质 //区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用: int bs1(int l,int r){ while(l>1; if(check(mid)) r=mid; else l=mid+1; } return l; } //区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用: int bs2(int l,int r){ while(l>1; if(check(mid)) l=mid; else r=mid-1; } return l; }
这个模板不仅是解决普通的在一个有序数组中找到目标的下标,而是更贴近于竞赛,也就是常说的“二分答案”。
举个例子:
#include #include using namespace std; int a[]={1,4,6,6,7,10,12,20}; int k=7; int main(){ int n=8; int l=0,r=n-1; while(l>1; if(a[mid]>=k) r=mid; else l=mid+1; } //l是大于等于k的第一个位置 if(a[l]==k) cout<<l; //4 else cout<<-1; return 0; }
说一下我的写法法:先写mid=l+r>>1,通过check来更新l或者r,如果r=mid,那么l=mid+1;如果l=mid,则r=mid-1,有减一就要加一,在mid上加一,即mid=l+r+1>>1。