月度归档：2019年12月

lower_bound/upper_bound简易实现

发表评论

lower_bound:

1
2
3
4
5
6
7
8
9
int lower_bound(int v) { //arr[1..n],arr[0..n-1]
    int l = 0, r = n-1,mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (arr[mid]<v)l=mid+1;
        else r = mid;
    }
    return l;
}

upper_bound:

1
2
3
4
5
6
7
8
9
int upper_bound(int v) { //arr[1..n],arr[0..n-1]
    int l = 0, r = n-1,mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (arr[mid]<=v)l=mid+1;
        else r = mid;
    }
    return l;
}