Wednesday, March 27, 2013

[LeetCode] Search for a Range

Thought:
Find the largest index whose value is not more than target.

Code:
public class Solution {
    public int[] searchRange(int[] A, int target) {
       
        int[] ret = new int[2];
        ret[0] = helper(A, target - 1);
        ret[1] = helper(A, target);
        if (ret[1] != -1 && A[ret[1]] == target) ret[0]++;
        if (ret[0] != -1 && A[ret[1]] != target) ret[0] = ret[1] = -1;

        return ret;
    }   
    public int helper (int[] a, int x) {
        int start = 0;
        int end = a.length - 1;
        int mid = (start + end)/2;
        int result = -1;

        while (start <= end) {
            if (a[mid] > x) {
                end = mid - 1;
                mid = (start + end)/2;
            }else {
                start = mid + 1;
                result = mid;
                mid = (start + end)/2;
            }
        }
        return result;
    }
}

No comments:

Post a Comment