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

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

题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

设计并实现时间复杂度为 O(log n) 的算法

输入输出样例

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

输入：nums = [], target = 0
输出：[-1,-1]

算法一，使用一次二分找到目标位置再迭代找到左端点和右端点

 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;
        }
        

算法二，使用两次二分，查找左端点和右端点

//使用两次二分查找对应的上界和下界
        vector<int> searchRange2(vector<int>&nums,int target)
        {
    
            if(nums.empty())
            {
    
                return {
    -1,-1};
            }

            //建立二分查找的值
            int left=0,right=nums.size()-1;

            //查找元素第一次出现的位置

            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;


            //查找元素最后一次出现的位置
            left=0;
            right=nums.size()-1;

            while(left<right)
            {
    
                //避免死循环
                int mid=(left+right+1)/2;

                if(nums[mid]<=target)
                {
    
                    left=mid;
                }
                else if(nums[mid]>target)
                {
    
                    right=mid-1;
                }
            }
            //之前已经判断重载所以无需再次判断查找是否失败
            int rightIndex=right;

            return {
    leftIndex,rightIndex};
        }