# [leetcode] Search for a Range

### Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return `[-1, -1]`.

For example,
Given `[5, 7, 7, 8, 8, 10]` and target value 8,
return `[3, 4]`.

tags: array, binary search

```class Solution {
public:
vector<int> searchRange(int A[], int n, int target) {
vector<int> re;
_searchRange(re, A, 0, n, target);
return re;
}
void _searchRange(vector<int> &result, int A[], int start, int end, int target){
int mid = (start + end) / 2;
result.push_back(-1);
result.push_back(-1);
return;
}
else if(A[mid] == target){//found
int left = mid;
int right = mid;
while(A[left] == target && left >= start){
left--;
}
left++;//important
while(A[right] == target && right < end){
right++;
}
right--;//important
result.push_back(left);
result.push_back(right);
return;
}
else{
if(A[mid] > target){
_searchRange(result, A, start, mid, target);
}
else{
_searchRange(result, A, mid + 1, end, target);
}
}

}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.