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

几个月前找实习的时候刷过这道题，这几天突然碰到了结果忘了，重新记录一下

leetcode题目地址

题目简单来说是在升序的数组中找到等于target的第一个元素和最后一个元素

思路也比较简单，第一个大于target的数的前一位就是最后一个元素 , 第一个小于target的元素的后一个就是第一个元素。

于是代码如下

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
45
class Solution {
public:
    //找到第一个小于target的后一个位置
    int binarySearchEx1(vector<int>& nums, int target){
        int l=0;int r=nums.size()-1;
        int ans=-1;
        while(l<=r){
            int mid = (r-l)/2+l;
            if(nums[mid]>=target){
                r=mid-1;
                
            }else{
                l=mid+1;
                ans=mid;
            }
        }   
        return ans+1;
    }
    // Ex2 找到第一个比target大的位置的前一个
    int binarySearchEx2(vector<int>& nums, int target){
        int l=0;int r=nums.size()-1;
        int ans=nums.size();
        while(l<=r){
            int mid = (r-l)/2+l;
            if(nums[mid]>target){
                r=mid-1;
                ans=mid;
            }else{
                l=mid+1;
            }
        }
        return ans-1;

    }
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ret(2,-1);
        if(nums.size()==0) return ret;
        ret[0] = binarySearchEx1(nums,target);
        ret[1] = binarySearchEx2(nums,target);
        if(ret[0]<=ret[1]&&ret[0]>=0&&ret[0]<=nums.size()&&nums[ret[0]]==target&&nums[ret[1]]==target)
        return ret;

        return vector<int>{-1,-1};
    }
};

还有更多优化的方法，比如Ex1和Ex2可以合成一个，可以参考leetcode的题解