Search for a Range 题解
题目来源：https://leetcode.com/problems/search-for-a-range/description/
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
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
Solution
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res(2, -1);
if (nums.empty())
return res;
int size = nums.size();
int low = 0, high = size - 1, mid;
while (low <= high) {
if (target < nums[low] || target > nums[high])
return res;
mid = (low + high) / 2;
if (target == nums[mid])
break;
if (target < nums[mid])
high = mid;
if (target > nums[mid]) {
if (mid + 1 <= size - 1)
low = mid + 1;
else
return res;
}
}
auto temp = mid;
while (temp - 1 >= 0 && nums[temp - 1] == target)
temp--;
res[0] = temp;
temp = mid;
while (temp + 1 <= size - 1 && nums[temp + 1] == target)
temp++;
res[1] = temp;
return res;
}
};
解题描述
这道题题意是，在一个排好序的数组中查找一个目标数字所在的区间。用到的算法首选二分查找，上面是我一开始的解法，不过时间复杂度较高，二分查找只是用于找到一个目标数字的位置，然后再向两边探测边界。
看了评论区的解答后改进了算法，将查找分成了二分查找下界和上界两步：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res(2, -1);
if (nums.empty())
return res;
int size = nums.size();
int low = 0, high = size - 1, mid;
while (low < high) {
mid = (low + high) / 2;
if (target > nums[mid])
low = mid + 1; // 向右逼近，以找到下界
else
high = mid;
}
// 判断下界是否是目标元素所在，不是的话说明找不到目标元素
if (nums[low] != target)
return res;
res[0] = low;
high = size - 1;
while (low < high) {
mid = (low + high) / 2 + 1; // 多+1，让中间位置偏向右边，防止陷入死循环
if (target < nums[mid])
high = mid - 1; // 向左逼近，以找到上界
else
low = mid;
}
res[1] = high;
return res;
}
};