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

题目描述

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

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

进阶：

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 0≤nums.length≤1050 \leq nums.length \leq 10^5
  • −109≤nums[i]≤109-10^9 \leq nums[i] \leq 10^9
  • nums是一个非递减数组nums \quad 是一个非递减数组
  • −109≤target≤109-10^9 \leq target \leq 10^9

解题思路

这道题我一开始的思路是用二分法去求得一个target对应的下标index，然后再从index开始向左向右去扫描得到left和right。

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int binarySearch(vector<int>& nums,int target,int left,int right)
{
    int mid=(left+right)/2;
    if(nums[mid]==target) return mid;
    if(left>right) return -1;
    if(nums[mid]<target)
    {
        return binarySearch(nums,target,mid+1,right);
    }
    else{
        return binarySearch(nums,target,left,mid-1);
    }
}

vector<int> searchRange(vector<int>& nums, int target)
{
    if(nums.empty()) return {-1,-1};
    int index=binarySearch(nums,target,0,nums.size()-1);
    if(index==-1) return {-1,-1};
    int left=index;
    int right=index;

    while((right+1<nums.size())&&(nums[right]==nums[right+1]))
    {
        right++;
    }

    while((left>0)&&(nums[left]==nums[left-1]))
    {
        left--;
    }
    return {left,right};
}

但是这样子的最好时间复杂度为O(logn)O(logn)，最坏时间复杂度为O(n)O(n)，不满足条件。

如果要达到O(logn)O(logn)的时间复杂度，那么就要用二分法分别求出下界left和上界right。

其中的关键主要是每一次迭代过程中left和right的更新，如果想求上界，那么只有当nums[mid]>target时才更新right为mid-1；如果想求下界，那么就要在nums[mid]>=target时就更新right为mid-1。对left的更新也类似。但是，按照这种方法更新得到的上界会大1，需要减掉。

具体细节见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int binarySearch(vector<int>& nums,int target,bool findLeft)
{
    int left=0;
    int right=nums.size()-1;
    int ans=nums.size();
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(nums[mid]>target||(findLeft&&nums[mid]>=target))
        {
            right=mid-1;
            ans=mid;
        }
        else{
            left=mid+1;
        }

    }
    return ans;
}

vector<int> searchRange(vector<int>& nums, int target)
{
    if(nums.empty()) return {-1,-1};
    int left=binarySearch(nums,target,true);
    int right=binarySearch(nums,target,false)-1;
    //cout<<left<<" "<<right<<endl;
    if(left<nums.size()&&right<nums.size()&&nums[left]==nums[right]) return {left,right};
    return {-1,-1};
    
}

时间复杂度为：O(logn)O(logn)

空间复杂度为：O(1)O(1)