# LeetCode Search for a Range

LeetCode Search for a Range

Given an array of integers sorted in ascending order, 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]`.

```class Solution {
private:
int lowerbound(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (nums[m] < target)l = m + 1;
else if (nums[m] >= target)r = m - 1;
}
return l;
}

int upperbound(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (nums[m] <= target)l = m + 1;
else if (nums[m] > target)r = m - 1;
}
return r;
}
public:
vector<int> searchRange(vector<int>& nums, int target) {
int lower = lowerbound(nums, target), upper = upperbound(nums, target);
if (lower <= upper)return vector<int>({ lower, upper });
else return vector<int>({ -1,-1 });
}
};
```

```class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.size() == 0)return vector<int>({ -1,-1 });
vector<int>::iterator lower = lower_bound(nums.begin(), nums.end(), target), upper = upper_bound(nums.begin(), nums.end(), target) - 1;
if (lower <= upper)return vector<int>({ lower - nums.begin(), upper - nums.begin() });
else return vector<int>({ -1,-1 });
}
};
```