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