Search for a Range
最后更新于：2022-04-01 22:58:07
**一. 题目描述**
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of `O(logn)`.
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]`.
**二. 题目分析**
题目大意是，给定一个已排序的序列和一个目标数字`target`，在这个序列中寻找等于`target`的**元素的下标范围**。由于序列已经排好序，直接用二分查找，分别求等于`target`的最靠左的元素下标`left`和最靠右的元素下标`right`即可。
**三. 示例代码**
~~~
#include
#include
using namespace std;
class Solution {
public:
vector searchRange(vector& nums, int target) {
int n = nums.size();
int left = searchRangeIndex(nums, target, 0, n - 1, true);
int right = searchRangeIndex(nums, target, 0, n - 1, false);
vector result;
result.push_back(left);
result.push_back(right);
return result;
}
private:
int searchRangeIndex(vector& nums, int target, int low, int high, bool isLeft)
{
while (low <= high)
{
int midIndex = (low + high) >> 1;
if (nums[midIndex] == target)
{
int temp = -1;
if (isLeft)
{
if (nums[midIndex] == nums[midIndex - 1] && low < midIndex)
temp = searchRangeIndex(nums, target, low, midIndex - 1, true);
}
else
{
if (nums[midIndex] == nums[midIndex + 1] && high > midIndex)
temp = searchRangeIndex(nums, target, midIndex + 1, high, false);
}
return temp == -1 ? midIndex : temp; // temp == -1时表示只有中间一个值等于target
}
else if (nums[midIndex] > target)
high = midIndex - 1;
else
low = midIndex + 1;
}
return -1; // 找不到target，输出-1
}
};
~~~
**四. 小结**
注意题目要求`O(logn)`的时间复杂度，算法写的不好可能会超时。
';