Accepted Java solution with binary search


  • 2
    M
    public int[] searchRange(int[] nums, int target) {
        int midPos = binarySearch(nums, 0, nums.length - 1, target);
        if(midPos == -1) return new int[] {-1,-1};
        else{
            int leftRange = midPos - 1, rightRange = midPos + 1, tmp;
            while((tmp = binarySearch(nums, 0, leftRange, target)) != -1){
                leftRange = tmp - 1;
            }
            while((tmp = binarySearch(nums, rightRange, nums.length - 1, target)) != -1){
                rightRange = tmp + 1;
            }
            return new int[]{leftRange + 1, rightRange - 1};
        }
    }
    
    public int binarySearch(int nums[], int start, int end, int target){
        int i = start, j = end, mid;
        while(start <= end){
            mid = start + (end - start) / 2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] < target)
                start = mid + 1;
            else end = mid - 1;
        }
        return -1;
    }

Log in to reply
 

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