34.在排序数组中寻找元素的第一个和最后一个位置

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array

示例 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 是一个非递减数组
• nums 是一个非递减数组

思路分析：

这也是一道典型的二分查找的问题，与之前不同的是，需要找出元素第一次出现的位置和最后一次出现的位置，而若是元素没有出现过的话，需要返回数组[-1,-1]，这里可以在最后利用一个判断语句进行判断，如下：

 if (a <= b && b < (int)nums.size() && nums[a] == target && nums[b] == target)
        {
            return vector<int>{a, b};
        }
        return {-1,-1};

那么总的套路还是一样的，仍然可以参考我之前总结的二分查找的多个不同模板进行求解。

(3条消息) 【LeetCode704.二分查找】——二分查找方法汇总_一粒蛋TT的博客-CSDN博客

左分右边法：

class Solution {
public:
    //求出第一次出现位置
    int target(vector<int>& nums, int target) {
        int l = -1;
        int r = (int)nums.size();
        while ((l + 1) != r)
        {
            int m = (l + r) / 2;
            //cout << "m=" << m<<endl;
            if (nums[m] < target)
            {
                l = m;
            }
            else
            {
                r = m;
            }
        }
        cout << "target1=" << r << endl;
        return r;
    }
    //求出最后一次出现的位置
    int targettwo(vector<int>& nums, int target)
    {
        int l = -1;
        int r = (int)nums.size();
        while ((l + 1) != r)
        {
            int m = (l + r) / 2;
            //cout << "m=" << m<<endl;
            if (nums[m] <= target)
            {
                l = m;
            }
            else
            {
                r = m;
            }
        }
        cout << "target2=" << l << endl;
        return l;
    }

    vector<int> searchRange(vector<int>& nums, int target )
    {
        int a = this->target(nums, target );
        int b = this->targettwo(nums, target );
        if (a <= b && b < (int)nums.size() && nums[a] == target && nums[b] == target)
        {
            return vector<int>{a, b};
        }
        return {-1,-1};
    }
};

左闭右闭法：

class Solution { 
public:
    int binarySearch(vector<int>& nums, int target, bool lower) {
        int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
            return vector<int>{leftIdx, rightIdx};
        } 
        return vector<int>{-1, -1};
    }
};

利用STL库：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) {
            return {-1, -1};
        }
        int leftIdx = lower_bound(nums.begin(), nums.end(), target)-nums.begin();
        int rightIdx = upper_bound(nums.begin(), nums.end(), target)-1-nums.begin();
        if(leftIdx<=rightIdx && rightIdx<nums.size() && nums[leftIdx]==target && nums[rightIdx]==target) {
            return {leftIdx, rightIdx};
        }
        return {-1, -1};
    }
};

利用CPP中的STL库函数，我们可以更快的直接求出元素的第一次出现位置以及最后一次出现的位置。这部分代码参考了leetcode随心源的题解。

总的来说，该题是对之前简单二分查找的一个延伸拓展。

后续也会坚持更新我的LeetCode刷题笔记，欢迎大家关注我，一起学习。
如果这篇文章对你有帮助，或者你喜欢这篇题解，可以给我点个赞哦。
CSDN同步更新，欢迎关注我的博客：一粒蛋TT的博客_CSDN博客-LeetCode学习笔记,HTML+CSS+JS,数据结构领域博主

往期回顾：
LeetCode367.有效的完全平方数
LeetCode69.x的平方根
LeetCode35.搜索插入位置
LeetCode704.二分查找