MENU

二分模板

February 21, 2019 • Read: 2564 • 算法阅读设置

二分模板一共有两个,分别适用于不同情况

算法思路:假设目标值在闭区间$[L,R]$中,每次将区间长度缩小一半,当$L = R$时,我们就找到了目标值

版本1

当区间$[L,R]$的更新操作是$r = mid; l = mid + 1$

这种方式使得中点$mid$属于左半区间,则左半区间是$[L, mid]$,右半区间是$[mid + 1, R]$

int binary(int l, int r) {
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (check(mid))
            r = mid; // 左
        else
            l = mid + 1; // 右
    }
    return l;
}

例题:LeetCode 275. H-Index II

版本2

当区间$[L,R]$的更新操作是$r = mid - 1; l = mid$时

这种方式使得中点$mid$属于右半区间,则左半区间是$[L,mid - 1]$,右半区间是$[mid,R]$

int binary(int l, int r) {
    while (l < r) {
        int mid = 1 + l + ((r - l) >> 1);
        if (check())
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

例题:LeetCode 69. Sqrt(x)

Last Modified: March 23, 2019
Archives Tip
QR Code for this page
Tipping QR Code