本题是一个和二分查找相关的综合性问题,大致思路就是分别找到目标值在数组中的左边界和右边界,再返回区间即可。
问题可分为如下三种情况:
① target 在 nums 数组的最值范围之外,即 target < nums[0] || target > nums[n-1],此时应该返回 {-1, -1};
② target 在 nums 数组的最值范围之内,但是数组中不存在 target,此时也应该返回 {-1, -1};
③ 数组中存在 target,此时应该返回对应的区间范围。
我们规定左(右)边界为不包含 target 的左(右)边界,代码实现如下:
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int l = getLeftBorder(nums, target); int r = getRightBorder(nums, target); if(l == -2 || r == -2) // 情况1 return {-1, -1}; else if(r - l > 1) // 情况3,根据我们先前的定义,若nums中有target,r-l至少为2 return {l + 1, r - 1}; return {-1, -1}; // 情况2 } // 寻找右边界 int getRightBorder(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int res = -2; // 一开始笔者把默认值设为-1,但若target的值正好为nums的最小值,默认值就和最终的区间值冲突了 while(left <= right) { int mid = left + ((right - left) / 2); // 等价于(left + right) / 2,防止溢出 if(target < nums[mid]) { right = mid - 1; } else { left = mid + 1; res = left; } } return res; } // 寻找左边界 int getLeftBorder(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int res = -2; while(left <= right) { int mid = left + ((right - left) / 2); if(target <= nums[mid]) { right = mid - 1; res = right; } else { left = mid + 1; } } return res; } };