One binary search, very simple idea


  • -1
    B

    The idea is to run binary search once, and try to find the position of target. If it is not found, return [-1,1]. If we find the position, we set return [i,j]=[pos, pos], and move j right till the value is not target, and move i left till the value is not target.

       public int[] searchRange(int[] nums, int target) {
            int[] range = new int[]{-1,-1};
            if(nums == null || nums.length < 1) return range;
            int low = 0;
            int high = nums.length - 1;
            while(low <= high){
                int mid = (low + high) / 2; 
                if(nums[mid] < target) low = mid + 1;
                else if(nums[mid] > target) high = mid - 1;
                else{
                    range[0] = mid;
                    range[1] = mid;
                    break;
                }
            }
            if(range[0] == -1) return range;
            while(range[0]> 0 && nums[range[0] - 1] == target) {
                range[0] = range[0]-1;
            }
            while(range[1]< nums.length-1 && nums[range[1]+1] == target) {
                range[1] = range[1]+1;
            }
            return range;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.