two time binary search solution


  • 0
    M

    public int[] searchRange(int[] nums, int target) {
    int[] res = new int[2];
    Arrays.fill(res,-1);
    if(nums == null || nums.length == 0) return res;

        int len = nums.length;
        int left = 0;
        int right = len -1;
        while(left+1<right) {
            int mid = left + (right-left)/2;
            if(nums[mid]==target) {
                res[0]=getleft(nums, left, mid, target);
                res[1]=getright(nums, mid, right, target);
                return res;
            } else if(nums[mid]<target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        // left and right two element is target
        if(nums[left] == target) {
            res[0] = left;
            if(nums[right] == target) {
                res[1] = right;
            } else {
                res[1] = left;
            }
        } else {
            if(nums[right] == target) {
                res[0] = right;
                res[1] = right;
            }
        }
        return res;
    }
    public int getleft(int[] nums, int left, int endl, int target) {
        int res = 0;
        if(nums[left] == target) { 
            res = left;
            return res; }
        if(nums[endl] == target) res=endl;
        while(left+1 < endl) {
            int midl = left+(endl-left)/2;
            if(nums[midl]<target) {
                left = midl;
            } else {
                endl = midl;
            }
        }
        if(nums[left] == target) { res = left; }
        else if(nums[endl] == target) res=endl;
        return res;
    }
    public int getright(int[] nums, int beginr, int right, int target) {
        int res = 0;
        if(nums[right] == target) { 
            res = right;
            return res; }
        if(nums[beginr] == target) res=beginr;
        while(beginr+1 < right) {
            int midr = beginr+(right-beginr)/2;
            if(nums[midr]>target) {
                right = midr;
            } else {
                beginr = midr;
            }
        }
        if(nums[right] == target) { res = right; }
        else if(nums[beginr] == target) res=beginr;
        return res;
    }

Log in to reply
 

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