题目描述
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].
Example1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
解题思路
- 普通的二分
- 注意二分循环结束的条件，begin <= end,这一点一直卡了很久。。。
C++代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res;
res.push_back(findFirstK(nums, target));
res.push_back(findLastK(nums, target));
return res;
}
int findFirstK(vector<int> nums, int target){
int begin = 0;
int end = nums.size() - 1;
int mid = 0;
while(begin <= end){
mid = (begin + end) / 2;
if(nums[mid] == target){
if((mid > 0 && nums[mid - 1] != target) || mid == 0){
return mid;
}else {
end = mid - 1;
}
}
else if(nums[mid] < target){
begin = mid + 1;
}else if(nums[mid] > target){
end = mid - 1;
}
}
return -1;
}
int findLastK(vector<int> nums, int target){
int begin = 0;
int end = nums.size() - 1;
int mid = 0;
while(begin <= end){
mid = (begin + end) / 2;
if(nums[mid] == target){
if((mid < nums.size() - 1 && nums[mid + 1] != target) || (mid == nums.size() - 1)){
return mid;
}else{
begin = mid + 1;
}
}
else if(nums[mid] < target){
begin = mid + 1;
}else if(nums[mid] > target){
end = mid - 1;
}
}
return -1;
}
};
