整数二分查找算法模板

二分查找算法

二分算法有两个模板，分别适用于不同的情况。

模板1

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

int bsearch_1(int l,int r){
    while(l < r){
        int mid = l + r >> 1; // 找出中间值的下标
        if(check(mid)) r = mid; // 划分为[l, mid]
        else l = mid + 1; // 划分为[mid + 1, r]
    }
    return l;
}

模板2

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

int bsearch_2(int l,int r){
    while(l < r){
        int mid = l + r + 1 >> 1; // 找出中间值的下标
        if(check(mid)) l = mid; // 划分为[mid, r]
        else r = mid - 1; // 划分为[l, mid - 1]
    }
    return l;
}