常见STL函数用法

常用STL函数用法

关于二分

lower_bound ：中间 $ if $ 判断是 $ if (a[mid] < ans) $
upper_bound：中间 $ if $ 判断是 $ if (a[mid] <= ans) $

代码lower_bound：

ans = lower_bound(a +1 , a + 1 + n , a[val]) - a - 1 ;

//二分的区间是a[]数组里的[l,r] 找的是tar
int lower_bound(int a[],int l,int r,int ans) {
    while(l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] < ans) l = mid + 1 ;
        else r = mid - 1 ;
    }
    return l ;
}

代码upper_bound：

ans = upper_bound(a + 1 , a +1 + n , a[val] ) - 1 - a ;

//二分的区间是a[]数组里的[l,r] 找的是ans
int uppbou(int a[] , int l , int r , int ans) {
    while(l<=r){
        int mid=(l+r)/2;
        if (a[mid]<=tar) l=mid+1;
        else r=mid-1;
    }
    return l;
}