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

发表于： 分类于：
字数： 1158 阅读：≈ 3分钟

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

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

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

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

思路

基本思想

如果不要求时间复杂度的话，可以直接使用遍历的方式，从左到右遍历，第一个相等的元素的位置就是开始位置，最后一个不相等的元素的前一个位置就是结束位置，但是本题中强调了时间复杂度

由于是排序数组，所以可以考虑二分查找，先找到相等的元素

找到之后，向左的第一个不相等位置的下一个位置就是开始位置，向右的第一个不相等位置的前一个位置就是结束位置

查找开始和结束位置时需要注意，防止下标越界，到了数组的两端就会强制结束，此时会有两种情况，一种是两端的位置时开始或结束位置

此时nums[right]==target或者nums[right]==target

数组的两端就是目标，如果只是单纯的到了数组两端，并且数组两端的元素并不是，目标，此时就需要执行left+1或者right-1，理解下面的代码即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int left=index,right=index;
//增加left!=0是为了防止下标越界
while(nums[left]==target && left!=0){
    left--;
}
//找到了开始位置，判断是到了开头结束还是不相等结束
index=nums[left]==target?left:left+1;
res[0]=index;
//增加right!=nums.size()-1是为了防止下标越界
while(nums[right]==target && right!=nums.size()-1){
    right++;
}
//找到了结束位置,判断是到了末尾结束还是不相等结束
index=nums[right]==target?right:right-1;
res[1]=index;

while循环结束就需要分情况讨论，直接使用三目运算符分情况

执行流程

代码

根据以上分析，得出以下代码：

 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
34
35
36
37
38
39
40
41
42
43
44

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        //找到目标元素的大概位置
        int index=binarySearch(nums,0,nums.size()-1,target);
        vector<int> res(2,-1);
        if(index==-1){
            return res;
        }else{
            int left=index,right=index;
            //增加left!=0是为了防止下标越界
            while(left!=0&&nums[left]==target){
                left--;
            }
            //找到了开始位置，判断是到了开头结束还是不相等结束
            index=nums[left]==target?left:left+1;
            res[0]=index;
            //增加right!=nums.size()-1是为了防止下标越界
            //应该先判断下标是否越界，然后再访问元素
            while(right!=nums.size()-1&&nums[right]==target){
                right++;
            }
            //找到了结束位置,判断是到了末尾结束还是不相等结束
            index=nums[right]==target?right:right-1;
            res[1]=index;
        }
        return res;
    }
    int binarySearch(vector<int> &nums,int begin,int end ,int target){
        if(begin>end)
            return -1;
        else{//范围合法
            int index=(begin+end)/2;
            if(nums[index]>target){//目标在左边
                return binarySearch(nums,begin,index-1,target);
            }
            else if(nums[index]<target){//目标在右边
                 return binarySearch(nums,index+1,end,target);
            }else{//找到目标
                return index;
            }
        }
    }
};

总结

规定了时间复杂度，则使用二分查找找到对应的位置，然后为了下标越界，到了数组两端强制结束搜索，此时需要判断是到了数组两端强制结束还是遇到了不相等的元素，有下面两种情况：

  1. nums=[1,1,1,1],target=1,此时因为到了数组两端强制结束
  2. nums=[1,2,2,3],target=2，此时因为遇到了不相等元素结束