徐州网站建设求职简历,网络服务商主要包括什么,分分钟采集wordpress,网站关键词的写法在排序数组中查找元素的第一个和最后一个位置一、题目链接二、题目三、题目解析四、算法原理五、编写代码六、总结二分模板一、题目链接
在排序数组中查找元素的第一个和最后一个位置
二、题目 三、题目解析
“非递减顺序排列”#xff1a;要么是递增要么是不动。
对于空数…
在排序数组中查找元素的第一个和最后一个位置一、题目链接二、题目三、题目解析四、算法原理五、编写代码六、总结二分模板一、题目链接
在排序数组中查找元素的第一个和最后一个位置
二、题目 三、题目解析
“非递减顺序排列”要么是递增要么是不动。
对于空数组是不能非法访问的直接返回[-1,-1]这算一个特殊处理。
四、算法原理
解法一暴力查找。遍历数组找到目标值后用begin标记再遍历到最后一个目标值并用end标记返回begin和end的下标。最差情况完整遍历一遍都没找到所以时间复杂度是O(n)。未利用数组有序的特性 解法二朴素二分
若用朴素二分mid正好是目标值但是若该值是目标区间的中间值那么还要向左向右查找目标值区间[begin,end]最差情况在下面第二张图那么此时O(logn)的时间复杂度就会降为O(n)。
二分查找算法的本质就是二段性。 开始位置(begin)和结束位置(end)不能同时查找所以可以先找一个位置。在朴素二分的基础上进行修正。
查找区间的左端点 查找区间的右端点 五、编写代码
class Solution {
public:vectorint searchRange(vectorint nums, int target) {// 处理边界情况if (nums.size() 0) return { -1, -1 };int begin 0;// 1.二分左端点int left 0, right nums.size() - 1;while (left right){int mid left (right - left) / 2;if (nums[mid] target) left mid 1;else right mid;}// 判断是否有结果if (nums[left] ! target) return { -1, -1 };else begin left;// 标记左端点left写成right也行left right已经相遇了// 2.二分右端点left 0, right nums.size() - 1;// 没必要写 left 0 这一句while (left right){int mid left (right - left 1) / 2;if (nums[mid] target) right mid - 1;else left mid;}// 左端点都有了右端点一定有return { begin, right };}
};六、总结二分模板
