34. find the first and last positions of elements in the sorted array - binary search, double pointer

One 、 Title Description

Given an array of integers in ascending order nums, And a target value target. Find the start 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].

Advanced ：

• You can design and implement time complexity of O(log n) Does the algorithm 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]

Two 、 Problem solving

Two points search

This problem needs to be advanced O(log(n)) Time complexity of , So I thought of binary search , If you find a target number in an ascending non repeating array, it is easier to write , Here the array numbers are repeated , So it can be divided into finding the position where the target value first appears in the array , And then looking for the second place , However, the position of the second occurrence can be changed to the target value +1 The position of the first occurrence in the array , Then the position is -1.

class Solution {
    
    public int[] searchRange(int[] nums, int target) {
    
        // Sorted array  log(n)  Two points search 
        if(nums == null || nums.length == 0){
    
            return new int[]{
    -1,-1};
        }
        int start = binsearch(nums,target);
        int end = binsearch(nums,target+1)-1;
        // Yes start  and  end  Make boundary judgment 
        if(start == nums.length  || nums[start] != target){
    
            return new int[]{
    -1,-1};
        }else{
    
            return new int[]{
    start,end};
        }
    }

    // Two points search 
    public int binsearch(int[] nums,int target){
    
        int left = 0,right = nums.length;
        while(left < right){
    
            int mid = left + (right - left) / 2;
            // If the median value is less than the target value   Look to the right 
            if(nums[mid] < target){
    
                left = mid + 1;
            }else if(nums[mid] == target){
    
                // The target value is equal to the median value   Find on the left 
                right = mid;
            }else{
    
                // Look to the left 
                right = mid;
            }
        }
        return left;
    }
}

Traverse left and right

Double pointer traversal , Define two pointers to traverse from left to right and from right to left respectively , If you find the value that appears for the first time , Record the subscript .

class Solution {
    
    public int[] searchRange(int[] nums, int target) {
    
        // Traverse left and right 
        int[] res = new int[]{
    -1,-1};
        int left = 0,right = nums.length - 1;
        if(nums == null || nums.length == 0){
    
            return res;
        }
        // Traverse from left to right 
        for(int i = left;i<=right;i++){
    
            if(nums[i] == target){
    
                res[0] = i;
                break;
            }
        }
        // Traverse from right to left 
        for(int i = right;i>=left;i--){
    
            if(nums[i] == target){
    
                res[1] = i;
                break;
            }
        }
        return res;
    }
}