The idea is to define an array with size 2 to store lower and higher range. Implement binary search to locate the index.
public class Solution {
public int[] searchRange(int[] A, int target) {
int[] res = new int[2];
res[0] = -1;
res[1] = -1;
if(A == null || A.length == 0){
return res;
}
searchRangeOps(A, target, 0, A.length - 1, res);
return res;
}
private void searchRangeOps(int[] A, int target, int begin, int end, int[] res){
if(begin > end){
return;
}
int mid = (begin + end) / 2;
if(begin == end){
if(A[begin] == target){
if(begin < res[0] || res[0] == -1){
res[0] = begin;
}
if(end > res[1] || res[1] == -1){
res[1] = end;
}
}
return;
}
if(target > A[mid]){
searchRangeOps(A, target, mid + 1, end, res);
}else if(target < A[mid]){
searchRangeOps(A, target, begin, mid - 1, res);
}else{
int index1 = mid;
int index2 = mid;
while(index1 >= begin && A[index1] == target){
index1--;
}
while(index2 <= end && A[index2] == target){
index2++;
}
index1++;
if(index1 < res[0] || res[0] == -1){
res[0] = index1;
}
index2--;
if(index2 > res[1] || res[1] == -1){
res[1] = index2;
}
return;
// if(mid < res[0] || res[0] == -1){
// res[0] = mid;
// }
// if(mid > res[1] || res[1] == -1){
// res[1] = mid;
// }
//searchRangeOps(A, target, begin, mid - 1, res);
//searchRangeOps(A, target, mid + 1, end, res);
}
}
}
没有评论:
发表评论