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

港控/mmm° 2022-10-08 05:49 101阅读 0赞

> 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
> 
> 如果数组中不存在目标值 target，返回 \[-1, -1\]。
> 
> 示例 1：
> 
> 输入：nums = \[5,7,7,8,8,10\], target = 8  
> 输出：\[3,4\]  
> 示例 2：
> 
> 输入：nums = \[5,7,7,8,8,10\], target = 6  
> 输出：\[-1,-1\]  
> 示例 3：
> 
> 输入：nums = \[\], target = 0  
> 输出：\[-1,-1\]

class Solution {
        public int first=Integer.MAX_VALUE;
        public int end=Integer.MIN_VALUE;
        public int[] searchRange(int[] nums, int target) {
            if(nums==null||nums.length==0){
                return new int[]{-1,-1};
            }
            
            helper(nums,target,0,nums.length-1);
             
            if(first==Integer.MAX_VALUE){
               return new int[]{-1,-1};
            }
            
            if(end==Integer.MIN_VALUE){
                return new int[]{first,-1};
            }
              return new int[]{first  ,end};
        }
            public void helper(int [] nums,int target,int left,int right){
                if(left>right||left<0||right>=nums.length) return ;
                int mid=left+(right-left)/2;
                if(nums[mid]==target){
                        if(mid<first){
                            first=mid;
                           
                        }
                        if(mid>end){
                            end=mid;
                            
                        }
    
                }
                if(nums[mid]>=target){
                     helper(nums,target,left,mid-1);
                }
                if(nums[mid]<=target){
                     helper(nums,target,mid+1,right);
                }
                return;
    
            }
    }