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

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

描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。

找出给定目标值在数组中的开始位置和结束位置。

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

进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例

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

题解

1. 暴力

class Solution {
    
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        
    // 1、遍历
        int n = nums.size();
        int left = -1;	//左边界
        int right = -1; //右边界
        for ( int i = 0; i < n; ++i){
      // 从左往右遍历
            if (nums[i] == target){
    
               if (left == -1){
    
                   left = i;
                   right = i;
               }
               else{
    
                   right = i;
               }
           }    
        }
        return vector<int>{
    left,right};
    }
};

2. 二分查找

时间复杂度： $O(\log n)$，其中 nn 为数组的长度。二分查找的时间复杂度为 $O(\log n)$，一共会执行两次，因此总时间复杂度为 $O(\log n)$。

空间复杂度：$O(1)$ 。只需要常数空间存放若干变量。

class Solution {
    
public:
    vector<int> searchRange(vector<int>& nums, int target) {
    
        // 找到第一个等于或大于target的数
        int left = 0, right = nums.size() - 1;
        while(left <= right){
    
            int mid = (left + right) >> 1;
            if(nums[mid] >= target){
    
                right = mid - 1;
            }else{
    
                left = mid + 1;
            }
        }
        int start = right + 1;

        // 找到最后一个小于或等于target的数
        left = start, right = nums.size() - 1;
        while(left <= right){
    
            int mid = (left + right) >> 1;
            if(nums[mid] <= target){
    
                left = mid + 1;     // left 为 找到第一个大于target的数
            }else{
    
                right = mid - 1;
            }
        }
        int end = left - 1;     // left - 1为最后一个小于或等于target的数

        if (start <= end){
          // left > right 不存在target
            return vector<int> {
    start, end};
        }
        return vector<int> {
    -1, -1};

    }
};