每次写二分都要纠结于边界。。。总结一下。。。
/* 二分三种情况总结：（默认数组的元素是升序） */ int bs(int num) //求满足条件的一个，不管它的位置。。。 { int l=1, r=n, mid, tmp; while(l<=r) { mid = (l+r)>>1; tmp = query(mid); if(tmp==num) return mid; else if(tmp>num) l = mid+1; else r = mid-1; } return -1; //表示没有满足的。。 } int bs1(int num) //求满足条件的最靠前的一个。。返回l。。 { int l=1, r=n, mid; while(l<=r) { mid = (l+r)>>1; if(query(mid)>=num) r = mid-1; else l = mid+1; } return l; //如果求(>=num)的最靠前一个就这样就好 } //如果求(==num)的最靠前一个就在最后加一个特判就好。。。 int bs2(int num) //求满足条件的最靠后的一个。。返回r。。 { int l=1, r=n, mid; while(l<=r) { mid = (l+r)>>1; if(query(mid)<=num) l = mid+1; else r = mid-1; } return r; }