Leetcode 34. Find First and Last Position of Element in Sorted Array 在一个有序数组中找到第一个和最后一个元素

解决思路：

利用二分法来进行位置的查找，主要涉及两个函数int lower_bound(nums, target) 和 int upper_bound(nums, target); 分别找到target的第一个和最后一个位置。

其中主要有一下几个方面需要注意：

1）nums为空的情况；直接返回{-1, -1};

2)nums中只有一个元素时，注意lower_bound和upper_bound中的while(l < r)应该改为while(l <= r)，否则无法进入while循环，导致结果错误；

3）一般的二分查找，在求mid时，我们习惯于用（left + right）/ 2,但是当left和right数值很大时，(left+right)可能会溢出，因此这里采用的是 left + (right - left) / 2;

//主要代码：
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty())      //如果nums为空，则返回{-1, -1}
            return {-1, -1};
        int low = lower_bound(nums, target);   //得到low位置
        int high = upper_bound(nums, target);  //得到lhigh位置
        if (low == high)           //如果low == high,说明nums中没有和target元素
            return {-1, -1};
        else 
            return {low, high - 1};
    }
    int lower_bound(vector<int>& nums, int target)
    {
        int l = 0, r = nums.size() - 1;
        while(l <= r)
        {
            int mid = l + (r - l) / 2;   //防止l+r溢出
            if(nums[mid] >= target)
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }
    int upper_bound(vector<int>& nums, int target)
    {
        int l = 0, r = nums.size() - 1;
        while(l <= r)
        {
            int mid = l + (r - l) / 2;  //防止l+r溢出
            if(nums[mid] <= target)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return l;
    }
};