Standard Java solution using binary search


  • 0
    W
    public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        int start = 0;
        int end = 0;
        int res[] = new int[2];
        res[0] = -1;
        res[1] = -1;
        while(left <= right){
            mid = (left + right)/2;
            if(nums[mid] == target){
                start = mid;
                while(start > 0 && nums[start] == nums[start-1]){
                    start--;
                }
                end = mid;
                while(end < nums.length -1 && nums[end] == nums[end + 1]){
                    end++;
                }
                res[0] = start;
                res[1] = end;
                break;
            }
            else if(nums[mid] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        return res;
    }
    }

  • 0
    Y

    This is "partially" binary search, improvement can be made after target is found. Think about the test case {1,1,....,1} and target 1, the time complexity is O(n).


  • 0
    W

    Thanks very much for your comment, you mean that I should check the end point? Thanks for your advice


Log in to reply
 

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