题目链接：

链接: 在排序数组中查找元素的第一个和最后一个位置.

题目描述：

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回[-1, -1]。

时间复杂度为 O(n) 的解决方案这里不再赘述了，以下展示的是时间复杂度为 O(log n) 的解决方案

测试样例：

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

初级题解：

二分找到target，然后前后遍历找到头尾。

@Override
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int len = nums.size();
        int left = 0, right = len - 1;
        vector<int>ans;
        while(left <= right)
        {
            int mid = (left + right) >> 1;
            if(nums[mid] == target)
            {
                int fir = mid, last = mid;
                while(fir >= 0 && nums[fir] == target) fir--;
                while(last < len && nums[last] == target) last++;
                ans.push_back(fir + 1);
                ans.push_back(last - 1);
                return ans;
            }
            else if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid - 1;
        }
        ans.push_back(-1);
        ans.push_back(-1);
        return ans;
    }
};

升级题解：

对普通二分查找稍作修改。先找到第一个>=target的位置，再找到第一个>=target+1的位置，就可以基本确定区间了。

@Override
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = searchFirst(nums, target);
        int r = searchFirst(nums, target + 1);
        if(l == nums.size() || nums[l] != target)
            return {-1,-1};
        return {l, r - 1};
    }
    int searchFirst(vector<int>& nums, int target) {    //找第一个>=target的
        int left = 0, right = nums.size();
        while(left < right)
        {
            int mid = (left + right) >> 1;
            if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] >= target)
                right = mid;
        }
        return left;
    }
};