二分法模板

二分法的模板

模板一：

当mid在绿色区域，也就是 a[mid]>=target。使用下列模板：

区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：

public void way1(int l,int r,int target){
        while (l < r) {
            int mid = (l + r) >> 1;
            if (a[mid] >= target) r = mid;
            else l = mid + 1;
        }
    }

模板二

当min在红色区域，也就是a[mid]<=target.使用下列模板。

区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：

public void way2(int l,int r,int target){
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (a[mid] <= target) l = mid; 
            else r = mid - 1;
        }
    }