企业官网建设流程全解析

题目描述

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

解题思路总览

方法一：二分查找（左边界 + 右边界）

代码实现

classSolution{public:vector<int>searchRange(vector<int>&nums,inttarget){if(nums.empty())return{-1,-1};// 找左边界（第一个 >= target 的位置）intstart=findLowerBound(nums,target);// 检查左边界是否有效if(start==nums.size()||nums[start]!=target){return{-1,-1};}// 找右边界（第一个 > target 的位置，然后减1）intend=findLowerBound(nums,target+1)-1;return{start,end};}private:intfindLowerBound(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]>=target){right=mid-1;}else{left=mid+1;}}returnleft;}};

核心思想

本题本质是查找 target 的左边界和右边界：

1. 左边界：第一个 >= target 的位置
2. 右边界：第一个 > target 的位置减1

利用二分查找的变体，通过nums[mid] >= target来收缩右边界，逐步逼近左边界。

算法流程图

以 nums = [5,7,7,8,8,10], target = 8 为例： 第一步：找左边界（第一个 >= 8 的位置） 初始：left=0, right=5 第1轮：mid=2, nums[2]=7 < 8，left=mid+1=3 第2轮：mid=4, nums[4]=8 >= 8，right=mid-1=3 第3轮：mid=3, nums[3]=8 >= 8，right=mid-1=2 left=3, right=2，循环结束 返回 left = 3（左边界） 第二步：找右边界（第一个 > 8 的位置减1） 找 > 8，实际上就是找第一个 >= 9 的位置 调用 findLowerBound(nums, 9) 初始：left=0, right=5 第1轮：mid=2, nums[2]=7 < 9，left=mid+1=3 第2轮：mid=4, nums[4]=8 < 9，left=mid+1=5 第3轮：mid=5, nums[5]=10 >= 9，right=mid-1=4 left=5, right=4，循环结束 返回 left = 5，然后 end = 5 - 1 = 4（右边界） 结果：[3, 4]

逐行解析

if(nums.empty())return{-1,-1};

处理空数组边界情况，直接返回 [-1, -1]。

intstart=findLowerBound(nums,target);

调用辅助函数找到 target 的左边界（第一个 >= target 的位置）。

if(start==nums.size()||nums[start]!=target){return{-1,-1};}

两种情况说明 target 不存在于数组中：

1. start == nums.size()：说明所有元素都小于 target
2. nums[start] != target：说明 start 位置的值大于 target（因为 start 是第一个 >= target 的位置）

intend=findLowerBound(nums,target+1)-1;

找右边界：第一个 > target 的位置 = 第一个 >= target+1 的位置，减 1 得到右边界。

为什么要用 target+1？因为数组是整数，可以通过找 target+1 的左边界来间接找到 > target 的位置。

intfindLowerBound(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]>=target){right=mid-1;}else{left=mid+1;}}returnleft;}

找左边界（第一个 >= target 的位置）的核心逻辑：

• nums[mid] >= target：说明左边界在 [left, mid] 区间（包括 mid），更新 right = mid - 1
• nums[mid] < target：说明左边界在 [mid+1, right] 区间，更新 left = mid + 1

循环结束后，left 就是第一个 >= target 的位置。

复杂度分析

方法二：直接使用 lower_bound（STL 思想）

代码实现

classSolution{public:vector<int>searchRange(vector<int>&nums,inttarget){if(nums.empty())return{-1,-1};// 使用 STL lower_bound 找左边界autolower_it=lower_bound(nums.begin(),nums.end(),target);// 检查左边界是否有效if(lower_it==nums.end()||*lower_it!=target){return{-1,-1};}// 使用 STL upper_bound 找右边界autoupper_it=upper_bound(nums.begin(),nums.end(),target);intstart=lower_it-nums.begin();intend=upper_it-nums.begin()-1;return{start,end};}};

核心思想

直接利用 C++ STL 的两个标准库函数：

• lower_bound：返回第一个 >= target 的迭代器
• upper_bound：返回第一个 > target 的迭代器

STL 原理简析

lower_bound的实现逻辑与手动实现完全相同：

template<classForwardIt,classT>ForwardItlower_bound(ForwardIt first,ForwardIt last,constT&value){ForwardIt it;while(first<last){it=first+(last-first)/2;if(*it<value){first=it+1;}else{last=it;}}returnfirst;}

复杂度分析

方法三：手动实现 lower_bound 和 upper_bound

代码实现

classSolution{public:vector<int>searchRange(vector<int>&nums,inttarget){if(nums.empty())return{-1,-1};intstart=myLowerBound(nums,target);if(start==nums.size()||nums[start]!=target){return{-1,-1};}intend=myUpperBound(nums,target)-1;return{start,end};}private:intmyLowerBound(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}else{right=mid-1;}}returnleft;}intmyUpperBound(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]<=target){left=mid+1;}else{right=mid-1;}}returnleft;}};

myLowerBound vs myUpperBound 对比

算法流程图

myLowerBound(nums, target)： 目标：找第一个 >= target 的位置 条件：nums[mid] < target -> left = mid + 1 否则 -> right = mid - 1 myUpperBound(nums, target)： 目标：找第一个 > target 的位置 条件：nums[mid] <= target -> left = mid + 1 否则 -> right = mid - 1 以 nums = [5,7,7,8,8,10], target = 8 为例： myLowerBound(nums, 8)： 找第一个 >= 8，返回 3 myUpperBound(nums, 8)： 找第一个 > 8，返回 5 end = 5 - 1 = 4 结果：[3, 4]

复杂度分析

边界情况分析

情况1：数组为空

输入: nums = [], target = 0 分析: nums.empty() 为 true，直接 return {-1, -1} 结果: [-1, -1]

情况2：target 小于所有元素

输入: nums = [5,7,7,8,8,10], target = 3 分析: 找左边界 findLowerBound(nums, 3) 逐步向右移动，最终 left = 0 但 nums[0] = 5 != 3 结果: [-1, -1]

情况3：target 大于所有元素

输入: nums = [5,7,7,8,8,10], target = 100 分析: 找左边界 findLowerBound(nums, 100) 逐步向左移动，最终 left = 6 = nums.size() start == nums.size() 结果: [-1, -1]

情况4：target 只出现一次

输入: nums = [5,7,7,8,8,10], target = 10 分析: 左边界：找到 10 在位置 5 右边界：找第一个 > 10，即第一个 >= 11 找不到，upper = 6，end = 6 - 1 = 5 结果: [5, 5]

情况5：target 充满整个数组

输入: nums = [8,8,8,8], target = 8 分析: 左边界：findLowerBound(nums, 8) = 0 右边界：findLowerBound(nums, 9) - 1 = 4 - 1 = 3 结果: [0, 3]

情况6：target 不存在但夹在两个数之间

输入: nums = [5,7,7,8,8,10], target = 9 分析: 左边界：findLowerBound(nums, 9) 第1轮：mid=2, nums[2]=7 < 9，left=3 第2轮：mid=4, nums[4]=8 < 9，left=5 第3轮：mid=5, nums[5]=10 >= 9，right=4 left=5, right=4，循环结束 返回 left = 5，但 nums[5] = 10 != 9 结果: [-1, -1]

面试追问 FAQ

相关题目

总结