LeetCode--34.在排序数组中查找元素第一个和最后一个位置(二分法)

在排序数组中查找元素第一个和最后一个位置(C++）

1. 题目描述

难度：中等

2. 题目分析

看到题目我们需要知道以下几点：

数组是有序的数组中存在重复的元素算法时间复杂度必须是O(logn)级别目标元素可能不存在与数组中

根据题目要求，算法复杂度必须是O(logn)级别，那么二分法就是最佳的算法。根据本题，我们要寻找的是目标元素在数组的起始位置和结束位置，我们可以根据二分法先搜索目标元素的起始位置，然后以该起始位置为起点，在搜索结束位置即可。时间复杂度为O(logn)

3. C++语言实现

代码如下：

class Solution {public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> res(2,-1);// 如果数组为空，直接返回[-1,-1]if(nums.empty()) return res;// 初始化变量int n=nums.size(),l=0,r=n-1;// 循环条件是左下标<右下标while(l<r){int m=l+(r-l)/2;if(nums[m]>=target) r=m;else l=m+1;}// 如果nums[l]!=target，说明目标不存在，返回[-1,-1]if(nums[l]!=target) return res;// 否则l即目标元素的起始位置res[0]=l;// 寻找右节点r=n;while(l<r){int m=l+(r-l)/2;if(nums[m]<=target) l=m+1;else r=m;}res[1]=l-1;return res;}};

运行结果为：

如果觉得《LeetCode--34.在排序数组中查找元素第一个和最后一个位置(二分法)》对你有帮助，请点赞、收藏，并留下你的观点哦！