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].
Discussion
查找目标在一个有序整数数组中的起止位置。算法的时间复杂度要求在O(logn)。
这个问题和在一个有序数组中查找元素类似。我们可以采用二分查找法分两次查找。第一次查找起始位置，第二次查找结束位置。只不过需要在判断的时候稍作改变。
查找起始位置的时候，如果中间元素小于目标元素，就在右侧查找，否则在左侧查找。（这里与查找一个元素不同的是中间元素等于目标元素的情况，如果中间元素等于目标元素，则在左侧查找。）
查找结束位置的时候，如果中间元素大于目标元素，就在左侧查找，否在在右侧查找。
算法的时间复杂度为O(logn)。
C++ Code
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> answer = {-1, -1};
if(nums.size() == 0)
{
return answer;
}
answer[0] = searchStart(nums, target, 0, nums.size() - 1);
answer[1] = searchEnd(nums, target, 0, nums.size() - 1);
return answer;
}
/**
**查找起始位置
**/
int searchStart(vector<int> & nums, int target, int leftPos, int rightPos)
{
if(nums[leftPos] == target)
{
return leftPos;
}
if(rightPos - leftPos < 1)
{
return -1;
}
int middlePos = (leftPos + rightPos) / 2;
if(nums[middlePos] < target)
{
return searchStart(nums, target, middlePos + 1, rightPos);
}
else
{
return searchStart(nums, target, leftPos, middlePos);
}
}
/**
**查找结束位置
**/
int searchEnd(vector<int> & nums, int target, int leftPos, int rightPos)
{
if(nums[rightPos] == target)
{
return rightPos;
}
if(rightPos - leftPos < 1)
{
return -1;
}
int middlePos = (leftPos + rightPos + 1) / 2;
if(nums[middlePos] > target)
{
return searchEnd(nums, target, leftPos, middlePos - 1);
}
else
{
return searchEnd(nums, target, middlePos, rightPos);
}
return -1;
}
};