LeetCode #34

Description:

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].

Example:

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

Code:

``````class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.empty()) return vector<int> { -1, -1 };

int left = findLowerBound(nums, target);
int right = findUpperBound(nums, target) - 1;

if(left == nums.size() || nums[left] != target)
return vector<int>{-1, -1};
else
return vector<int>{left, right};
}

// 实现 lowerBound()
int findLowerBound(vector<int>& nums, int target){
int mid, start, end;
start=0;
end=nums.size();

while(start != end){
mid = start + (end - start)/2;
if(nums[mid] < target) start = mid + 1;
else end=mid;
}
return start;
}

// 实现 upperBound()
int findUpperBound(vector<int>& nums, int target){
int mid, start, end;
start=0;
end=nums.size();

while(start != end){
mid = start + (end - start)/2;
if(nums[mid] <= target) start = mid + 1;
else end=mid;
}
return start;
}
};
``````