【练习】【二分】力扣热题10034.在排序数组中查找元素的第一个和最后一个位置

题目

给你一个按照非递减顺序排列的整数数组 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]

来源：力扣热题100 34. 在排序数组中查找元素的第一个和最后一个位置

---

思路（注意事项）

---

纯代码 class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { vector<int> ans; int n = nums.size(); if (n == 0) return {-1, -1}; int l = 0, r = n - 1; while (l < r) { int mid = l + r >> 1; if (nums[mid] >= target) r = mid; else l = mid + 1; } if (nums[r] == target) ans.push_back(r); else { ans.push_back(-1); ans.push_back(-1); return ans; } l = 0; r = n - 1; while (l < r) { int mid = l + r + 1 >> 1; if (nums[mid] <= target) l = mid; else r = mid - 1; } ans.push_back(r); return ans; } }; 题解（加注释） class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { vector<int> ans; // 存储结果的数组 int n = nums.size(); // 数组的长度 // 如果数组为空，直接返回 {-1, -1} if (n == 0) return {-1, -1}; // 第一次二分查找：查找 target 的起始位置 int l = 0, r = n - 1; // 初始化左右指针 while (l < r) { int mid = l + r >> 1; // 计算中间位置 if (nums[mid] >= target) r = mid; // 如果中间值大于等于 target，缩小右边界 else l = mid + 1; // 否则缩小左边界 } // 检查是否找到 target if (nums[r] == target) ans.push_back(r); // 如果找到，将起始位置加入结果 else { ans.push_back(-1); // 如果没找到，返回 {-1, -1} ans.push_back(-1); return ans; } // 第二次二分查找：查找 target 的结束位置 l = 0; // 重置左指针 r = n - 1; // 重置右指针 while (l < r) { int mid = l + r + 1 >> 1; // 计算中间位置（注意 +1 防止死循环） if (nums[mid] <= target) l = mid; // 如果中间值小于等于 target，缩小左边界 else r = mid - 1; // 否则缩小右边界 } // 将结束位置加入结果 ans.push_back(r); return ans; // 返回结果 } };