Search for a Range
Given a sorted array of n integers, find the starting and ending position of a given target value.
If the target is not found in the array, return [-1, -1].
Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].
http://www.lintcode.com/en/problem/search-for-a-range/
Discussion
就是Binary Search问题的扩展,如果真的理解了binary search,这个题一点都不难,无非是用二分找出来target第一次出现的地方(就是binary search),和target最后一次出现的地方(跟上一种情况相反,A[mid]==target时向右查找)。
Solution
class Solution {
/**
*@param A : an integer sorted array
*@param target : an integer to be inserted
*return : a list of length 2, [index1, index2]
*/
public:
vector<int> searchRange(vector<int> &A, int target) {
// write your code here
int n = A.size();
vector<int> result (2, -1);
if(n == 0) return result;
int start = 0, end = n-1;
int mid;
while(start+1 < end) {
mid = start + (end-start)/2;
if(A[mid] == target) {//go to left part to find the first place.
end = mid;
} else if(A[mid] > target) {
end = mid;
} else {
start = mid;
}
}
if(A[start] == target) {//check start first (most left)
result[0] =start;
} else if (A[end] == target) {
result[0] =end;
} else {
return result;
}
start = 0;
end = n-1;
while(start+1 < end) {
mid = start + (end-start)/2;
if(A[mid] == target) {//go to right part to find the last place
start = mid;
} else if(A[mid] > target) {
end = mid;
} else {
start = mid;
}
}
if(A[end] == target) {//check right first, (most right)
result[1] = end;
} else if (A[start] == target) {
result[1] = start;
} else {
return result;
}
return result;
}
};