给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
二分法
蓝色标记左边区域,浅蓝色边框代表元素尚未着色,蓝色边框代表元素已经着色; 红色标记右边区域,浅红色边框代表元素尚未着色,红色边框代表元素已经着色;
二分查找起始状态:
代码
class Solution {
public:
int searchleft(vector<int>& nums, int target) {
int l = -1;
int r = nums.size();
while(l + 1 != r){
int mid = l + (r - l)/2;
if(nums[mid] >= target){
r = mid;
}
else{
l = mid;
}
}
return r;
}
int searchright(vector<int>& nums, int target) {
int l = -1;
int r = nums.size();
while(l + 1 != r){
int mid = l + (r - l)/2;
if(nums[mid] <= target){
l = mid;
}
else{
r = mid;
}
}
return l;
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftdex = searchleft(nums,target);
int rightdex = searchright(nums,target);
if(leftdex <= rightdex && rightdex < nums.size() && nums[leftdex] == target && nums[rightdex] == target){
return { leftdex , rightdex};
}
else{
return { -1 , -1};
}
}
};
库函数
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.empty()) {
return {-1, -1};
}
int leftIdx = lower_bound(nums.begin(), nums.end(), target)-nums.begin();
int rightIdx = upper_bound(nums.begin(), nums.end(), target)-1-nums.begin();
if(leftIdx<=rightIdx && rightIdx<nums.size() && nums[leftIdx]==target && nums[rightIdx]==target) {
return {leftIdx, rightIdx};
}
return {-1, -1};
}
};
标签:begin,vector,target,nums,int,mid,34,查找,排序
From: https://www.cnblogs.com/lihaoxiang/p/17505842.html