原题描述
+
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]
。
示例 1
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
原题链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
思路解析
+
毫无疑问,时间复杂度O(log n)和升序数组,提示了我们使用二分查找的解法。
普通的二分查找在找到target后立即返回,所以我们需要做变式,情况分为以下两种。
寻找左边界
还是得举个例子。假设nums=[5, 7, 7, 8, 8, 10],target=7,那么应用一次二分查找得到:
显然不能立即返回,应该让mid作为新的边界,再做一次二分查找,mid才能指向预期结果。
那么问题来了,我们只知道当mid指向了target应该仍然继续二分查找下去,但却不知道应该经过多少次查找为止。
当nums[mid]大于或等于target时(等于的情况也必须要挪动,因为要尽可能的逼近边界),我们一定会不断让higher向左挪动,使它将不断靠近lower。只有nums[mid]小于target时,我们才会向右挪动lower。此时由于我们已经知道nums[mid]不等于target,所以lower要挪动到mid+1的位置。
那么这种情况下,当lower和higher相撞,该点一定是左边界。因为lower的左边不是target,而higher也一直在尽可能的往左挪动。
寻找右边界
与上面过程相反,我们尽可能向右挪动lower,让其与higher相撞即可。即当nums[mid]小于或等于target时,要挪动lower。但如果复用上面的逻辑,每次挪动时令lower=mid+1,那么最终lower一定会与higher相撞于最后一个target的后一个位置。此时lower-1才是所求。
这样调用两次二分查找逻辑,就可以完成题目。实现时,为了能重用二分查找逻辑,可以增加一个参数来控制寻找左边界还是右边界。
复杂度分析
+
C++参考代码
+
class Solution {
public:
int find_boudary(vector<int>& nums, int target, bool left) {
int lower = 0;
int upper = nums.size();
while (lower < upper) {
int mid = (lower + upper) / 2;
if ((nums[mid] > target) || (left && nums[mid] == target)) {
upper = mid;
} else {
lower = mid + 1;
}
}
return lower;
}
vector<int> searchRange(vector<int>& nums, int target) {
int left_most = find_boudary(nums, target, true);
if (left_most == nums.size() || nums[left_most] != target) {
return {-1, -1};
}
int right_most = find_boudary(nums, target, false) - 1;
return {left_most, right_most};
}
};