​

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 关注专栏：LeetCode面试必备100题 （优质好文持续更新中……）🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

一、题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。

二、测试样例

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

输出：[3,4]

说明：在数组中， 只有两个 8 ，范围是 [3, 4]。

三、算法思路

从题目不难看出，应该向二分查找算法的方向思考，数组是按照升序排列，正好符合二分查找的前提条件。

那么，如何查找呢？

查找开始和结束位置，相当于查找目标值在数组中的下界和上界，所以可以直接采用 STL 中的算法 lower_bound 和 upper_bound 算法来求解。其中，lower_bound 计算的是下界，upper_bound计算的是上界。

四、代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

int main()
{
    int a[] = {5,7,7,8,8,10};
    vector<int>nums(a, a+6);
    Solution obj;
    vector<int>ans = obj.searchRange(nums, 8);
    cout<<ans[0]<<" "<<ans[1]<<endl;
    return 0;
}

五、复杂度分析

5.1 时间复杂度

时间复杂度为：O(logn)，在上述代码中，使用的是 STL 中的 lower_bound 和 upper_bound 函数，这两个函数使用的都是二分查找算法，一个查找下界，一个查找上界，其中，lower_bound 返回大于等于目标值的元素的指针，upper_bound 返回的是大于目标值的元素的指针。因为二分查找算法的时间复杂度为 O(logn)，故上述算法总的时间复杂度为O(logn)。

5.2 空间复杂度

空间复杂度为：O(1)，在上述代码中，仅仅使用到了两个变量 lt 和 rt，故总的空间复杂度为O(1)。

六、总结

本题主要考查二分查找算法的应用，当然，可以不使用 STL 中的函数，可以自行实现一下，加深理解。

CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

欢迎小伙伴们点赞👍、收藏⭐、留言💬