题目描述给你一个按照非递减顺序排列的整数数组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]解题思路方法二分查找核心思路左边界第一个等于 target 的位置右边界最后一个等于 target 的位置可以分别用两次二分查找找左边界用二分查找找第一个 target的位置找右边界用二分查找找第一个 target的位置再减1具体过程示例nums [5, 7, 7, 8, 8, 10],target 8找左边界第一个 8: left0, right5, mid2, nums[2]7 8 → left3 left3, right5, mid4, nums[4]8 8 → right3 left3, right3, mid3, nums[3]8 8 → right2 left3 right2结束左边界 left 3 ✅ 找右边界第一个 8: left0, right5, mid2, nums[2]7 8 → left3 left3, right5, mid4, nums[4]8 8 → left5 left5, right5, mid5, nums[5]10 8 → right4 left5 right4结束右边界 left - 1 4 ✅代码实现class Solution { public: vectorint searchRange(vectorint nums, int target) { int left lowerBound(nums, target); int right upperBound(nums, target) - 1; // 检查是否找到 if (left right right nums.size() nums[left] target) { return {left, right}; } return {-1, -1}; } private: // 找第一个 target 的位置 int lowerBound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; } // 找第一个 target 的位置 int upperBound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; } };更简洁的写法用 STLclass Solution { public: vectorint searchRange(vectorint nums, int target) { auto left lower_bound(nums.begin(), nums.end(), target); auto right upper_bound(nums.begin(), nums.end(), target); if (left nums.end() || *left ! target) { return {-1, -1}; } return {(int)(left - nums.begin()), (int)(right - nums.begin() - 1)}; } };复杂度分析维度复杂度说明时间复杂度O(log n)两次二分查找空间复杂度O(1)只用常数个变量关键细节1. 为什么用left right而不是left right这是左闭右开区间的二分模板int left 0, right nums.size(); // 注意 right 是 size不是 size-1 while (left right) { int mid left (right - left) / 2; if (nums[mid] target) left mid 1; else right mid; } return left;right初始为size表示开区间循环结束时left right就是答案2. 为什么upperBound返回left后要减1upperBound返回的是第一个 target 的位置所以右边界是upperBound - 1。3. 如何判断是否找到if (left right right nums.size() nums[left] target)left right确保区间有效right nums.size()确保不越界nums[left] target确保真的找到了4. 和「搜索旋转排序数组」的区别题目区别33. 搜索旋转排序数组旋转数组找 target34. 查找第一个和最后一个位置有序数组找 target 的边界总结要点说明核心思想两次二分查找找左边界和右边界左边界第一个 target的位置右边界第一个 target的位置减1时间复杂度O(log n)空间复杂度O(1)