Find the first element
Find the second element
Find values from sorted array with duplicate elements;
public int[] searchRange(int[] A, int target) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int[] result = new int[2];
result[0] = findFirstElement(A, 0, A.length-1, target);
result[1] = findSecondElement(A, 0, A.length-1, target);
return result;
}
private int findFirstElement(int[] array, int low, int high, int target) {
while (low <= high) {
int mid = (low + high)/2;
if (mid==low && array[mid] == target || array[mid]== target && array[mid-1] < array[mid]) {
return mid;
} else {
if (array[mid] >= target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return -1;
}
private int findSecondElement(int[] array, int low, int high, int target) {
while (low <= high) {
int mid = (low + high)/2;
if (mid == high && array[mid] == target || array[mid]==target && array[mid] < array[mid+1]) {
return mid;
} else {
if (array[mid] <= target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return -1;
}
No comments:
Post a Comment