1 题目
??找到目标出现的区间范围（Search for a range）
lintcode：题号——61，难度——medium
2 描述
??给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。如果目标值不在数组中，则返回[-1, -1]。
??样例1：
输入：数组 = []，target = 9
输出：[-1,-1]
解释：9不在数组中。
??样例2：
输入：数组 = [5, 7, 7, 8, 8, 10]，target = 8
输出：[3,4]
解释：数组的[3,4]子区间值都为8。
3 思路
??在已排序的数组中，寻找目标出现的范围，找到目标出现的初始和最后位置[1]，它们中间的区间即是目标区间，二分搜索套模版[2]，跑两次就能得到结果。
- 找到目标出现的初始位置；
- 找到目标出现的最后位置；
- 得到目标区间。
3.1 图解
输入：数组 = [5, 6, 7, 9, 9, 9, 10, 12]，target = 9
输出：[3,5]
解释：数组的[3,5]子区间值都为8。
graph TD
X[原数组 ‘5, 6, 7, 9, 9, 9, 10, 12‘] -- 寻找初始位置 --> A
A[‘5, 6, 7, 9, 9, 9, 10, 12‘] -- 中间位置元素‘9‘,等于目标元素‘9‘ -->A1
A1 -- 抛掉 --> B[\抛掉‘5‘\]
A1[‘5, 6, 7, 9‘] -- 中间位置元素‘6‘,小于目标元素‘9‘ --> A2
A -- end = mid --> C[/抛掉‘9, 9, 10, 12‘/]
A2[‘6, 7, 9‘] -- 中间位置元素‘7‘,小于目标元素‘9‘ --> A3
A3[‘7, 9‘] -- 先比头,再比尾部 --> A4[元素9初始下标3]
X -- 寻找最后位置 --> D[‘5, 6, 7, 9, 9, 9, 10, 12‘]
D -- 略,同左边 --> D1[元素9最后位置5]
A4 --> Y[区间3,5]
D1 --> Y
3.2 时间复杂度
??在n规模的问题上使用两次二分法，时间复杂度为O(2 * log n)，依然是O(log n)。
3.3 空间复杂度
??算法的空间复杂度为O(1)。
4 源码
??C++版本：
/**
* @param A: 已排序数组
* @param target: 目标值
* @return: 目标出现的区间范围
*/
vector<int> searchRange(vector<int> &A, int target) {
// write your code here
vector<int> result;
if (A.empty())
{
result.push_back(-1);
result.push_back(-1);
return result;
}
int startPos = -1;
int endPos = -1;
startPos = findFirstPos(A, target);
endPos = findLastPos(A, target);
result.push_back(startPos);
result.push_back(endPos);
return result;
}
int findFirstPos(vector<int> & A, int target)
{
int start = 0;
int end = A.size() - 1;
int mid = 0;
while (start + 1 < end)
{
mid = start + (end - start) / 2;
if (A.at(mid) >= target)
{
end = mid;
}
if (A.at(mid) < target)
{
start = mid;
}
}
if (A.at(start) == target)
{
return start;
}
if (A.at(end) == target)
{
return end;
}
return -1;
}
int findLastPos(vector<int> & A, int target)
{
int start = 0;
int end = A.size() - 1;
int mid = 0;
while (start + 1 < end)
{
mid = start + (end - start) / 2;
if (A.at(mid) <= target)
{
start = mid;
}
if (A.at(mid) > target)
{
end = mid;
}
}
if (A.at(end) == target)
{
return end;
}
if (A.at(start) == target)
{
return start;
}
return -1;
}