【Hot100】34. Find the first and last positions of elements in a sorted array

34. Find the first and last positions of the elements in the sort array
Medium question
Give you an answer The decreasing An array of integers arranged in sequence 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 .

Answer key ：
Within a range , Find a number , Ask to find the start and end positions of this element , The numbers in this range are monotonically increasing , That is, it has monotonic property , So you can use dichotomy to do .

Two bisections , The first dichotomy finds the first t>=target The location of , The second dichotomy looks for the last t<=target The location of .
If the search is successful, two position subscripts will be returned , Otherwise return to [-1,-1].

• Template I ： When we will interval [l, r] Divide into [l,mid] and [mid + 1, r] when , The update operation is r = mid perhaps l = mid + 1, Calculation mid There is no need to add 1, namely mid=(l+r)/2.
• Template II ： When we will interval [l, r] Divide into [l,mid−1] and [mid,r] when , The update operation is r=mid−1 perhaps l=mid, In order to prevent the dead cycle , Calculation mid Need to add 1, namely mid=(l+r+1)/2.

Be careful ：
When the left boundary is to be updated to l = mid when , Order mid =(l + r + 1)/2, Equivalent to rounding up , It won't be because r Take a special value r = l + 1 And fall into a dead circle .

class Solution {
    
    public int[] searchRange(int[] nums, int target) {
    
        if(nums.length == 0) {
    
            return new int[]{
    -1,-1};
        }
    
        int l = 0, r = nums.length - 1; // Dichotomous range 
        while( l < r)			        // Find the starting position of the element 
        {
    
            int mid = (l + r )/2;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if( nums[r] != target) {
    
            return new int[]{
    -1,-1}; // To find the failure 
        }
        int L = r;
        l = 0; 
        r = nums.length - 1;     // Dichotomous range 
        while( l < r)			        // Find the end position of the element 
        {
    
            int mid = (l + r + 1)/2;
            if(nums[mid] <= target ) l = mid;
            else r = mid - 1;
        }
        return new int[]{
    L,r};
    }
}

class Solution {
    
    public int[] searchRange(int[] nums, int target) {
    

        if(nums.length == 0){
    
            return new int[]{
    -1,-1};
        } 

        int l = 0, r = nums.length - 1; // Dichotomous range   Left and right closed 
        
        // Find the starting position of the element 
        while( l < r){
    
            int mid = (l + r )/2;
            if(nums[mid] >= target){
    
                r = mid;
            } else{
    
                l = mid + 1; 
            }                    
        }

        if( nums[r] != target){
    
            return new int[]{
    -1,-1}; // To find the failure 
        } 
        
        int L = r;
        l = 0; r = nums.length - 1;     // Dichotomous range 

        // Find the end position of the element 
        while( l < r)			        
        {
    
            int mid = (l + r + 1)/2; // Be careful 
            if(nums[mid] <= target ){
    
                l = mid;
            } else {
    
                r = mid - 1;
            }
        }
        return new int[]{
    L,r};
    }
}