Leetcode (34) -- find the first and last positions of elements in a sorted array

Leetcode（34）—— Find the first and last positions of the elements in the sort array

subject

Give you an array of integers in non decreasing order $nums$, And a target value $target$. Please find out the start position and end position of the given target value in the array .

If the target value does not exist in the array $target$, return $[-1,-1]$.

You must design and implement a time complexity of $O(\log n)$ The algorithm to solve this problem .

Example 1：

Input ：nums = [5,7,7,8,8,10], target = 8
Output ：[3,4]

Example 2：

Input ：nums = [5,7,7,8,8,10], target = 6
Output ：[-1,-1]

Example 3：

Input ：nums = [], target = 0
Output ：[-1,-1]

Tips ：

• $0$ <= nums.length <= $10^5$
• $-10^9$ <= nums[i] <= $10^9$
• nums It's a Non decreasing group
• $-10^9$ <= target <= $10^9$

Answer key

Method 1 ： Brute force

Ideas

​​   The intuitive idea must be to traverse from front to back . Record the first and last encounter with two variables $\text{target}$ The subscript , But the time complexity of this method is $O(n)$, The condition of ascending array arrangement is not used .

Code implementation

My own ：

class Solution {
    
public:
    vector<int> searchRange(vector<int>& nums, int target) {
    
        vector<int> ans(2, -1);
        int l = 0, r = nums.size()-1;
        while(l <= r){
    
            if(nums[l] == target){
    
                ans[0] = l;
                break;
            }
            l++;
        }
        if(l > r) return ans;
        while(l <= r){
    
            if(nums[r] == target){
    
                ans[1] = r;
                break;
            }
            r--;
        }
        return ans;
    }
};

Complexity analysis

Time complexity ：$O(n)$, among $n$ It's an array nums The length of
Spatial complexity ：$O(1)$

Method 2 ： Two points search

Ideas

​​   Because the array has been sorted , So the whole array is monotonically increasing , We can Use dichotomy to speed up the search process .

​​   consider $\text{target}$ Start and end positions , In fact, what we're looking for is in the array 「 The first is equal to $\text{target}$ The location of 」（ Write it down as $\text{leftIdx}$） and 「 The first one is greater than $\text{target}$ Minus one 」（ Write it down as $\text{rightIdx}$）.

​​   Binary search , seek $\text{leftIdx}$ That is to find the first greater than or equal to in the array $\text{target}$ The subscript , seek $\text{rightIdx}$ That is to find the first greater than in the array $\text{target}$ The subscript , Then subtract the subscript by one . The judgment conditions of the two are different , For code reuse , We define binarySearch(nums, target, lower) It means that $\text{nums}$ Binary search in array $\text{target}$ The location of , If $\text{lower}$ by $\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$, Then find the first one greater than or equal to $\text{target}$ The subscript , Otherwise, find the first greater than $\text{target}$ The subscript .

​​   Last , because $\text{target}$ May not exist in the array , So we need to recheck the two subscripts we get $\text{leftIdx}$ and $\text{rightIdx}$, See if they meet the requirements , If the conditions are met, return $[\text{leftIdx},\text{rightIdx}]$, Go back if you don't agree $[-1,-1]$.

Code implementation

Leetcode Official explanation ：

class Solution {
     
public:
    int binarySearch(vector<int>& nums, int target, bool lower) {
    
        int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
        while (left <= right) {
    
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
    
                right = mid - 1;
                ans = mid;
            } else {
    
                left = mid + 1;
            }
        }
        return ans;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
    
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
    
            return vector<int>{
    leftIdx, rightIdx};
        } 
        return vector<int>{
    -1, -1};
    }
};

Complexity analysis

Time complexity ：$O(\log n)$, among $n$ Is the length of the array . The time complexity of binary search is $O(\log n)$, It will be executed twice , So the total time complexity is $O(\log n)$
Spatial complexity ：$O(1)$