Force buckle 34 finds the first and last positions of elements in a sorted array

Power button 34 Find the first and last positions of the elements in the sort array

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].

The design and implementation time complexity is O(log n) The algorithm of

I/o sample

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

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

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

Algorithm one , Use one bisection to find the target location, and then iteratively find the left endpoint and the right endpoint

 vector<int>searchRange(vector<int>&nums,int target)
        {
    
            vector<int>res;
            int length=nums.size();
            int left=0,right=length-1;
            int numIndex=-1;
            
            if(length==1)
            {
    
                (nums[0]==target)?res={
    0,0}:res={
    -1,-1};
                return res;
            }

            while(left<=right)
            {
    
                int mid=(left+right)/2;
                if(nums[mid]==target)
                {
    
                    numIndex=mid;
                    break;
                }
                else if(nums[mid]<target)
                {
    
                    left=mid+1;
                }
                else{
    
                    right=mid-1;
                }
            }
            if(numIndex==-1)
            {
    
                res={
    -1,-1};
            }
            else
            {
    
                int leftIndex=numIndex;
                int rightIndex=numIndex;

                while(leftIndex>=0&&nums[leftIndex]==target)
                {
    
                    leftIndex--;
                }

                while(rightIndex<length&&nums[rightIndex]==target)
                {
    
                    rightIndex++;
                }
                res.push_back(leftIndex+1);
                res.push_back(rightIndex-1);
            }
            return res;
        }
        

Algorithm 2 , Use two bisections , Find the left endpoint and the right endpoint

// Use two bisections to find the corresponding upper and lower bounds 
        vector<int> searchRange2(vector<int>&nums,int target)
        {
    
            if(nums.empty())
            {
    
                return {
    -1,-1};
            }

            // Create values for binary lookups 
            int left=0,right=nums.size()-1;

            // Find where the element first appears 

            while(left<right)
            {
    
                int mid=(left+right)/2;
                if(nums[mid]>=target)
                {
    
                    right=mid;
                }
                else if(nums[mid]<target)
                {
    
                    left=mid+1;
                }
            }
            if(nums[left]!=target)
            {
    
                return {
    -1,-1};
            }
            int leftIndex=left;


            // Find where the element last appeared 
            left=0;
            right=nums.size()-1;

            while(left<right)
            {
    
                // Avoid the dead cycle 
                int mid=(left+right+1)/2;

                if(nums[mid]<=target)
                {
    
                    left=mid;
                }
                else if(nums[mid]>target)
                {
    
                    right=mid-1;
                }
            }
            // The overload has been determined before, so there is no need to judge whether the search fails again 
            int rightIndex=right;

            return {
    leftIndex,rightIndex};
        }