找到目标出现的区间范围(Search for a range)
lintcode:题号——61,难度——medium
给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。如果目标值不在数组中,则返回[-1, -1]。
样例1:
输入:数组 = [],target = 9
输出:[-1,-1]
解释:9不在数组中。
样例2:
输入:数组 = [5, 7, 7, 8, 8, 10],target = 8
输出:[3,4]
解释:数组的[3,4]子区间值都为8。
在已排序的数组中,寻找目标出现的范围,找到目标出现的初始和最后位置[1],它们中间的区间即是目标区间,二分搜索套模版[2],跑两次就能得到结果。
- 找到目标出现的初始位置;
- 找到目标出现的最后位置;
- 得到目标区间。
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输入:数组 = [5, 6, 7, 9, 9, 9, 10, 12],target = 9
输出:[3,5]
解释:数组的[3,5]子区间值都为8。
在n规模的问题上使用两次二分法,时间复杂度为O(2 * log n),依然是O(log n)。
算法的空间复杂度为O(1)。
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; }
寻找目标出现的初始or最后位置:https://blog.csdn.net/SeeDoubleU/article/details/118346371 ↩︎
经典二分搜索:https://blog.csdn.net/SeeDoubleU/article/details/118271548 ↩︎