Search for a Range(在升序数组中找到目标值的左右边界)leetcode34

雨点打透心脏的1/2处 2022-05-21 22:59 106阅读 0赞

Given an array of integers `nums` sorted in ascending order, find the starting and ending position of a given `target` value.

Your algorithm's runtime complexity must be in the order of *O*(log *n*).

If the target is not found in the array, return `[-1, -1]`.

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]

public int[] searchRange(int[] nums, int target) {
            int [] result=new int[]{-1,-1};
            if(nums.length<=0)
                return result;
            int index=searchIndex(nums,0,nums.length-1,target);
            System.out.println(index);
            if(index==-1)
                return result;
            int leftIndex=index;
            while(leftIndex!=0){
            if(leftIndex>0&&nums[leftIndex-1]<nums[leftIndex])
                break;
            leftIndex=searchIndex(nums,0,leftIndex-1,target);
            }
            int rightIndex=index;
            while(rightIndex!=nums.length-1){
            if(nums[rightIndex+1]>nums[rightIndex])
                break;
            rightIndex=searchIndex(nums,rightIndex+1,nums.length-1,target);
            }
            result[0]=leftIndex;
            result[1]=rightIndex;
            return result;
        }
        int searchIndex(int[] nums,int low,int high,int target){
            while(low<=high){
            int mid=low+(high-low)/2;
            if(nums[mid]==target)
                return mid;
            else if(nums[mid]<target)
                low=mid+1;
            else
                high=mid-1;
            }
            return -1;
        }