高端网站模板,沛县网络营销是什么,网络设计的任务是什么,哪里可以免费注册网站文章目录 1. 题目2. 算法原理2.1 暴力解法2.2 二分查找左端点查找右端点查找 3. 代码实现4. 二分模板 1. 题目 题目链接#xff1a;34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣#xff08;LeetCode#xff09; 给你一个按照非递减顺序排列的整数数组 nums#… 文章目录 1. 题目2. 算法原理2.1 暴力解法2.2 二分查找左端点查找右端点查找 3. 代码实现4. 二分模板 1. 题目 题目链接34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode 给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [5,7,7,8,8,10], target 8
输出[3,4]示例 2
输入nums [5,7,7,8,8,10], target 6
输出[-1,-1]示例 3
输入nums [], target 0
输出[-1,-1]提示
0 nums.length 105-109 nums[i] 109nums 是一个非递减数组-109 target 109
2. 算法原理
2.1 暴力解法
这里暴力解法也比较简单直接遍历整个数组记录第一次出现的位置和最后一次出现的位置时间复杂度为O(N)这里就不示例了。
2.2 二分查找
这里是不能够直接二分的直接二分我们还需要从中间再往两边搜索如果该数组里面的值全是目标值效率就会降为O(N)。 这里还是利用二段性我们可分开查找左右端点分两种情况即可
左端点查找
这里我们的判断条件是nums[midi] target和nums[midi] target 当midi落在左区间的的时候肯定是没有我们要寻找的值的我们让left midi1即可 当midi落在右区间的时候这个区域里面是有可能有我们的target不能让right midi - 1这样会导致错失我们的target所以直接让right midi即可 细节处理 循环条件left right 这里一共就三种情况有目标值、全是大于目标值、全是小于目标值 有结果left一直在不符合条件的区间移动right一直在符合条件的区间移动且不会超出这个区间 letf要执行每次都是执行的midi1所以当left跳出去的时候正好是在目标值处 所以left right时就是最终结果无需判断 全是大于target在次情况下左区间的条件一直都不会命中而right则一直在向left这边移动最后相遇的时候我们只需判断相遇处是不是target 全是小于target这个情况就和上面这个一样 如果我们在left right的时候判断了那么就会进入死循环无限命中右区间条件 求中点midi left (right - left)/2 我们求中点的时候采用left(right-left)/2这里是防止溢出这种与left(right-left1)/2的区别就是当数组为偶数的时候前者求的是靠左位置而后者是靠右位置 这个在普通二分是没什么影响的可是在我们求端点的时候进行最后一次操作 采用②求中点时命中右区间的条件则会陷入死循环 右端点查找
查找右端点和查找左端点思想一致 这个求中点的方式就采用left(right-left1)/2靠右位置
3. 代码实现
class Solution
{
public:vectorint searchRange(vectorint nums, int target){//检查空数组if(nums.size() 0) return {-1,-1};int left 0;int right nums.size()-1;int begin left;//查找左端点while(left right){int midi left(right-left)/2;if(nums[midi]target){left midi1;}else right midi;}//判断是否有结果if(nums[left] ! target) return {-1,-1};else begin left; //记录左端点//查找右端点//left 0; //可不用重置right nums.size()-1;while(leftright){int midi left(right-left1)/2;if(nums[midi]target){left midi;}else right midi-1;}return {begin,right};}
};4. 二分模板
查找区间左端点
while(leftright)
{int mid left (right -left)/2;if(...){left mid 1}else{right mid;}
}查找区间右端点
while(leftright)
{int mid left (right -left1)/2;if(...){left mid}else{right mid - 1;}
}当下面出现减肥的时候上面就用加一
