二分查找模板

/* 求第一个大于等于value的位置x, 即[first0, x)都小于value, [x, last0)都大于等于value */
int lower_bound( vector<int> nums, int first, int last, int value )
{
    while ( first < last )                          /* 当fisrt==last时终止,此时[first, last)是空集 */
    {
        int mid = first + (last - first) / 2;   /* 防止溢出 */
        if ( nums[mid] < value )
            first = mid + 1;                /* [first0, first)范围内的元素都小于value */
        else last = mid;                        /* [last, last0)范围内的元素都大于等于value */
    }
    return(first);
}


/* 求第一个大于value的位置x, 即[first0, x)都小于等于value, [x, last0)都大于value */
int upper_bound( vector<int> nums, int first, int last, int value )
{
    while ( first < last )
    {
        int mid = first + (last - first) / 2;
        if ( nums[mid] <= value )
            first = mid + 1;        /* [first0, first)范围内的元素都小于等于value */
        else last = mid;                /* [last, last0)范围内的元素都大于value */
    }
    return(first);
}


vector<int> searchRange( vector<int> & nums, int target )
{
    int first   = lower_bound( nums, 0, nums.size(), target );
    int last    = upper_bound( nums, 0, nums.size(), target );

    if ( first == last )
        return({ -1, -1 });
    else
        return({ first, last - 1 });
}