当前位置：首页 > news >正文

在排序数组中查找元素的一个位置和最后一个位置-力扣

news 2025/8/3 2:28:58

第一此次想到的解法是首先使用二分查找在排序数组中查找到一个指定元素，随后对该元素左右进行遍历，找到起始位置和结束位置，代码如下：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int size = nums.size();int min = 0;int max = size - 1;while(min <= max){int mid = min + (max - min)/2;if(target < nums[mid]){max = mid - 1;}else if(target > nums[mid]){min = mid + 1;}else{while(nums[min] != target){min++;}while(nums[max] != target){max--;}return {min,max};}}return {-1,-1};}
};

执行虽然通过，但测试用时并不是很理想，在代码随想录看到的解法是将题目分为三种情况：

情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}

采用二分法来分别寻找左边界和右边界，最终分情况进行return。代码如下：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int leftBorder = getLeftBorder(nums, target);int rightBorder = getRightBorder(nums, target);// 情况一if (leftBorder == -2 || rightBorder == -2) return {-1, -1};// 情况三if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};// 情况二return {-1, -1};}
private:int getRightBorder(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] > target) {right = middle - 1;} else { // 寻找右边界，nums[middle] == target的时候更新leftleft = middle + 1;rightBorder = left;}}return rightBorder;}int getLeftBorder(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新rightright = middle - 1;leftBorder = right;} else {left = middle + 1;}}return leftBorder;}
};

将上述代码的两个二分查找函数进行合并：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int leftBorder = getBorder(nums, target, true);int rightBorder = getBorder(nums, target, false);// 情况一if (leftBorder == -2 || rightBorder == -2) return {-1, -1};// 情况三if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};// 情况二return {-1, -1};}
private:int getBorder(vector<int>& nums, int target, bool flag) {int left = 0;int right = nums.size() - 1;int border = -2;while (left <= right){int middle = left + (right - left)/2;if(flag) { //flag = true，返回左边界if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新rightright = middle - 1;border = right;} else {left = middle + 1;}}else{if (nums[middle] > target) {right = middle - 1;} else { // 寻找右边界，nums[middle] == target的时候更新leftleft = middle + 1;border = left;}}}return border;}};