recording:34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
首先想到暴力遍历记录，但是复杂度为O(n),其次想到利用二分找到一个目标后开始向左右附近找，其实本质是二分加暴力，时间复杂度也不达到要求，不过能跑
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int i=0,j=0;
int left = 0;
int right = nums.size() - 1;
while (left <= right)
{
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle - 1;
}
else if(nums[middle] < target) {
left = middle + 1;
}
else{//找到一个target，开始往左 往右试探
i=middle;
j=middle;
while(i>0&&nums[i-1]==nums[i])//往左试探
{
i--;
}
while(j<nums.size()-1&&nums[j+1]==nums[j])//往右试探
{
j++;
}
return vector<int>{i,j};
}
}
return vector<int>{-1,-1};
}
};
纯二分的思路不是找目标数，而是找目标数的左右边界
- 先通过二分查找找到目标值。
- 然后再去查找它的左右边界。如果找的是它左边界，那么就继续向左面查找。
- 查找右边界同理。
- 查找左边界和右边界的方法几乎相同，因此我将它们写在一个函数中，用一个boolean类型判断它是否是左边界。
- 当查找到目标值后，判断我们想要查找的是否是左边界。如果是，就继续向目标值的左面查（right = mid - 1）；如果不是，就向右面查找。最后返回最终的边界值。
个人感觉这种最好理解
class Solution {
public:
int SerachTT(vector<int>& nums, int target,bool ifleft) {
int ref=-1;//标记
int left = 0;
int right = nums.size() - 1;
while (left <= right)
{
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle - 1;
}
else if(nums[middle] < target) {
left = middle + 1;
}
else{
//此时nums[middle] == target
ref=middle;
if(ifleft){//如果找到的这个是左边界了
right = middle - 1;//往左边走
}else{
left = middle + 1;//往右走
}
}
}
return ref;//找到的一个边界
}
vector<int> searchRange(vector<int>& nums, int target) {
int left=SerachTT(nums,target,true);//左边界
int right=SerachTT(nums,target,false);//右边界
return vector<int>{left,right};
}
};
