Given an array of integers nums 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 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
有序数组中查找target 的 首次 和 最后一次出现下标
这题我用的方法很蠢， 就是 二分找出target, 然后O(n) 的往前，往后 找 first 和 last. 如果target有大量重复, 速度就会很慢， 但是这题 case 比较友好。。。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans;
if(nums.empty()) return vector<int>{-1,-1};
//step 1 : binary search target
int begin = 0, end = nums.size()-1,mid = 0;
while(begin +1 < end){
mid = begin + (end - begin)/2;
if(nums[mid] > target)
end = mid;
else if(nums[mid] < target)
begin = mid;
else
break;
}
if(nums[begin]!= target && nums[mid] != target && nums[end] != target )
return vector<int>{-1,-1};
// step 2 : find first position
int initiate = 0;
if(nums[begin] == target)
initiate = begin;
else
initiate = nums[mid] == target? mid: end;
// 越界情况
while(initiate >=0 && nums[initiate]== target)
initiate--;
ans.push_back(++initiate);
// step3: find last position
//越界情况
while(nums[initiate]== target && initiate <= nums.size()-1 )
initiate++;
ans.push_back(initiate-1);
return ans;
}
};
我们显然不能面向case 编程， 该优化的还是要优化。
这里只需要对 binary search 做一些小的修改就好了
while(begin+1 < end){
mid = begin + (end- begin) /2;
if(nums[mid] >= target)
end = mid;
else if(nums[mid] < target)
begin = mid;
}
在find first position 的过程中，mid等于target 的时候， end 左移。
类似[1,2,3,3,3,3,3,3] --> [1,2,3,3,3]-->[1,2,3] 这样的过程
这样一般情况下,最后退出情况就是
begin < target, end= target,并且 begin, end 相邻。
比如[1,2,3,3,3,3,4] -->[2,3]
但是如果数组类似[2,2,2]的情况，begin 也有可能是first position
所以 我们这里 优先选择begin作为下标.
end = nums[begin] == target? begin: end;
ans.push_back(end );
find last postion 就是对[first element of target, ........, nums.size()-1]这个数组进行二分。
这是 数组内所有元素都大于等于target
所以 只要考虑将 begin 不断右移 ,
类似[2,2,2,2,2,3] --> [2,2,3]-->[2,3] 这种情况
使得最后退出条件是begin= target, end> target,begin,end相邻
同理，这里也要考虑[2,2,2]这种数组，
begin = nums[end] == target? end:begin;
ans.push_back(begin);
所以退出find last position 循环后， 优先选择end 作为 last element of target的下标。
完整代码如下。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans;
int begin = 0, end = nums.size()-1,mid= 0;
// find first
//
while(begin+1 < end){
mid = begin + (end- begin) /2;
if(nums[mid] >= target)
end = mid;
else if(nums[mid] < target)
begin = mid;
}
if( nums.empty() || (nums[begin] != target && nums[end] != target) )
return vector<int>{-1,-1};
end = nums[begin] == target? begin: end;
ans.push_back(end );
// find last
begin = end;
end = nums.size()-1;
while(begin +1<end){
mid= begin + (end-begin)/2;
if(nums[mid]> target)
end = mid;
else
begin = mid;
}
begin = nums[end] == target? end:begin;
ans.push_back(begin);
return ans;
}
};
