C++ 面试高频考点 力扣 34. 在排序数组中查找元素的第一个和最后一个位置 二分查找左右端点 题解 每日一题

这是封面原图，和AI弄的动图：

二分查找进阶，精准定位左右边界

上一篇博客C++ 面试高频考点 力扣 704.二分查找咱们用LeetCode 704题吃透了“朴素二分查找”，对付无重复元素的有序数组那是手到擒来。但要是数组里藏着重复元素，比如[1,2,2,2,3]，想找2第一次和最后一次出现的位置，朴素二分就像“摸到鱼却抓不住首尾”——明明能找到2，却没法确定它是不是边界，最后只能靠遍历补漏，时间复杂度又退回O(n)。

今天咱们就借着LeetCode 34题（在排序数组中查找元素的第一个和最后一个位置），拆解二分查找的“左右边界查找模板”。还是老规矩，从“为什么朴素二分不行”说起，再抓“二段性”这个核心，把边界查找的逻辑和细节扒得明明白白～

题目描述

题目链接：力扣 34. 在排序数组中查找元素的第一个和最后一个位置

题目描述：

示例 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]

提示：

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums 是一个非递减数组
• -10^9 <= target <= 10^9

先踩坑：朴素二分为什么搞不定重复元素？

咱们先试试用昨天的朴素二分套这道题。比如数组nums = [1,2,2,2,3]，target = 2：

1. 初始left=0，right=4，mid=2，nums[mid]=2 == target，按朴素二分的逻辑，直接返回2——但这只是2的中间位置，不是我们要的“第一个”或“最后一个”；
2. 要是想找第一个2，就得在找到mid=2后，继续往左找；想找最后一个2，就得继续往右找。可这样一来，就需要在二分结束后再遍历，最坏情况比如nums = [1,1,1,...,1]（1万个1），target=1，遍历一遍又回到O(n)，完全违背了二分O(log n)的初衷。

问题出在哪？昨天的朴素二分，把数组分成了“小于target”“等于target”“大于target”三部分，但面对重复元素时，“等于target”的部分是一个区间，我们需要的是这个区间的左右端点，而不是区间里的任意一个点。

所以，核心思路得变：不再找“等于target的点”，而是用“二段性”把数组分成“一定不包含左端点”和“可能包含左端点”两部分（找左边界时），或者“一定不包含右端点”和“可能包含右端点”两部分（找右边界时）。

第一步：找左边界——如何定位“第一个target”？

核心逻辑：重新定义“二段性”

找左边界的关键，是把数组分成两部分：

• 左半部分：所有元素 < target（一定不包含左边界）；
• 右半部分：所有元素 ≥ target（可能包含左边界）。

比如nums = [1,2,3,3,3,4,5]，target=3：

• 左半部分（< 3）：[1,2]；
• 右半部分（≥ 3）：[3,3,3,4,5]。

我们要找的“左边界”，就是右半部分的第一个元素（下标2）。只要每次通过mid判断，把左半部分（<target）全部舍弃，最终剩下的那个点，就是左边界。

具体步骤拆解

1. 初始化边界：left=0，right = nums.size()-1（和朴素二分一致，闭区间）。
2. 循环条件：left < right（重点！不是left <= right，后面解释）。
3. 计算mid：mid = left + (right - left)/2（防溢出，且这里必须用“向下取整”，后面说原因）。
4. 判断与缩范围：
   • 若nums[mid] < target：mid在左半部分（一定不包含左边界），直接舍弃左半，left = mid + 1；
   • 若nums[mid] ≥ target：mid在右半部分（可能包含左边界），不能舍弃mid，所以right = mid。
5. 循环结束后验证：此时left == right（因为循环条件是left < right，退出时必相等），但要确认这个点是不是target（比如数组全小于target时，left会指向最后一个元素，仍小于target）。

关键细节：为什么是left < right？为什么mid要向下取整？

咱们用三个场景验证，就能明白这些细节的必要性：

场景1：数组包含target（如nums=[1,2,3,3,3,4]，target=3）

• 初始left=0，right=5，mid=2（nums[2]=3 ≥3）→ right=2；
• 此时left=0 < right=2，继续循环，mid=0（nums[0]=1 <3）→ left=1；
• 此时left=1 < right=2，继续循环，mid=1（nums[1]=2 <3）→ left=2；
• 现在left=2 == right=2，循环退出。验证nums[2]=3 == target，左边界就是2。

场景2：数组全大于target（如nums=[4,5,6]，target=3）

• 初始left=0，right=2，mid=1（nums[1]=5 ≥3）→ right=1；
• 继续循环，mid=0（nums[0]=4 ≥3）→ right=0；
• 退出循环，left=0 == right=0，但nums[0]=4≠3，返回-1。

场景3：数组全小于target（如nums=[1,2,3]，target=4）

• 初始left=0，right=2，mid=1（nums[1]=2 <4）→ left=2；
• 继续循环，mid=2（nums[2]=3 <4）→ left=3；
• 退出循环，left=3 == right=3，但3超出数组下标（或nums[3]不存在），返回-1。

从这三个场景能看出：

• 循环条件用left < right：是为了让循环在left == right时退出，避免死循环。如果用left <= right，当left==right时会再进一次循环，此时mid=left=right，若nums[mid]≥target，right=mid，导致无限循环。
• mid必须向下取整（即left + (right-left)/2）：如果用向上取整（left + (right-left+1)/2），比如场景1中最后一步left=1，right=2，会算出mid=2（nums[2]=3≥3）→ right=2，此时left=1 < right=2，下次循环还是mid=2，陷入死循环。

第二步：找右边界——如何定位“最后一个target”？

右边界的逻辑和左边界对称，但细节上有反转，别搞混！

核心逻辑：对称的“二段性”

找右边界的关键，是把数组分成两部分：

• 左半部分：所有元素 ≤ target（可能包含右边界）；
• 右半部分：所有元素 > target（一定不包含右边界）。

还是用nums = [1,2,3,3,3,4,5]，target=3：

• 左半部分（≤ 3）：[1,2,3,3,3]；
• 右半部分（> 3）：[4,5]。

我们要找的“右边界”，就是左半部分的最后一个元素（下标4）。每次通过mid判断，把右半部分（>target）全部舍弃，最终剩下的点就是右边界。

具体步骤拆解

1. 初始化边界：left=0，right = nums.size()-1（和左边界一致）。
2. 循环条件：left < right（和左边界一致）。
3. 计算mid：mid = left + (right - left + 1)/2（重点！这里要用“向上取整”，和左边界相反）。
4. 判断与缩范围：
   • 若nums[mid] > target：mid在右半部分（一定不包含右边界），直接舍弃右半，right = mid - 1；
   • 若nums[mid] ≤ target：mid在左半部分（可能包含右边界），不能舍弃mid，所以left = mid。
5. 循环结束后验证：此时left == right，同样要确认这个点是不是target。

关键细节：为什么mid要向上取整？

还是用场景验证，比如nums=[1,2,3,3,3,4]，target=3：

• 初始left=0，right=5，mid=0 + (5-0+1)/2=3（nums[3]=3 ≤3）→ left=3；
• 此时left=3 < right=5，继续循环，mid=3 + (5-3+1)/2=4（nums[4]=3 ≤3）→ left=4；
• 此时left=4 < right=5，继续循环，mid=4 + (5-4+1)/2=5（nums[5]=4 >3）→ right=4；
• 退出循环，left=4 == right=4，验证nums[4]=3 == target，右边界就是4。

如果这里用向下取整（mid=left + (right-left)/2），比如最后一步left=4，right=5，会算出mid=4（nums[4]=3 ≤3）→ left=4，此时left=4 < right=5，下次循环还是mid=4，陷入死循环。

所以，右边界的mid必须向上取整，才能避免死循环——这是和左边界最核心的区别！

完整代码实现

结合左边界和右边界的逻辑，我们可以写出完整代码，注意处理“数组为空”“target不存在”等边缘情况：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {// 先处理特殊情况：数组为空，直接返回[-1,-1]if (nums.empty()) {return {-1, -1};}vector<int> result(2, -1); // 初始化结果为[-1,-1]int n = nums.size();int left = 0, right = n - 1;// 第一步：找左边界while (left < right) {// mid向下取整（左边界专用）int mid = left + (right - left) / 2;if (nums[mid] < target) {// 左半部分（<target）舍弃，left移到mid+1left = mid + 1;} else {// 右半部分（≥target）保留，right移到midright = mid;}}// 循环结束后，left==right，验证是否是targetif (nums[left] == target) {result[0] = left;} else {// 左边界都不是target，说明数组中没有target，直接返回[-1,-1]return result;}// 第二步：找右边界（左边界已确认存在，不用重新初始化left）right = n - 1; // 只需要重置rightwhile (left < right) {// mid向上取整（右边界专用）int mid = left + (right - left + 1) / 2;if (nums[mid] > target) {// 右半部分（>target）舍弃，right移到mid-1right = mid - 1;} else {// 左半部分（≤target）保留，left移到midleft = mid;}}// 右边界一定是target（因为左边界已存在）result[1] = right;return result;}
};

代码细节说明

1. 数组为空处理：一开始就判断nums.empty()，避免后面访问nums[left]时报错。
2. 左边界验证后直接返回：如果左边界不是target，说明数组中没有target，不用再找右边界，直接返回[-1,-1]，提高效率。
3. 右边界无需重置left：因为左边界已经是target的位置，右边界一定在左边界右侧，直接用左边界作为起点即可。

对比总结：三种二分模板的核心区别

为了帮大家理清思路，咱们把朴素二分、左边界二分、右边界二分的核心区别做成表格，方便对比记忆：

模板类型	核心目标	二段性划分	循环条件	mid计算方式（取整）	缩范围逻辑（关键）	结果验证
朴素二分	找任意一个target	<target / ==target / >target	left ≤ right	向下取整（防溢出）	nums[mid]==target→返回；<target→left=mid+1；>target→right=mid-1	循环内直接返回，没找到返回-1
左边界二分	找第一个target	<target / ≥target	left < right	向下取整	<target→left=mid+1；≥target→right=mid	循环后left==right，验证nums[left]==target
右边界二分	找最后一个target	≤target / >target	left < right	向上取整	>target→right=mid-1；≤target→left=mid	循环后left==right，验证nums[left]==target

记忆口诀：

• 左边界：找“第一个≥target”，mid向下取整，right=mid；
• 右边界：找“最后一个≤target”，mid向上取整，left=mid；
• 循环条件都是left < right，退出必相等，验证不可少。

避坑指南：这些错误别再犯！

1. mid取整错误：左边界用向上取整、右边界用向下取整，必陷入死循环。
2. 循环条件用left <= right：左边界/右边界模板中，会导致left==right时继续循环，进而死循环。
3. 忘记验证结果：比如数组全小于target时，左边界会指向最后一个元素，但该元素≠target，直接返回会出错。
4. 右边界重置left：找右边界时，left已经是左边界（target的位置），无需重置为0，否则会浪费时间。

没错最喜欢的模板

1. 左端点

while(left < right)
{int mid = left + (right - left)/2;if(.....)//判断条件left = mid + 1;elseright = mid;
}

2. 右端点

while(left < right)
{int mid = left + (right - left + 1)/2;if(.....)//判断条件left = mid;elseright = mid - 1;
}

如果下面出现-1的时候，上面就 +1

模板本质复盘——为什么“二段性”是万能钥匙？

看到这里，你可能会问：为什么不管是找左右边界，都能靠“二段性”解决？这就要回到二分查找的本质了。

二分查找的核心不是“找target”，而是“通过缩小范围，快速定位目标”，而“二段性”是实现这一目标的唯一前提——只要数组能被划分为“满足某条件”和“不满足某条件”的两部分，且两部分边界清晰，就能用二分查找。

我们再梳理三种模板的“二段性”本质：

模板类型	二段性本质（核心条件）	目标位置
朴素二分	条件A：nums[mid] == target（唯一）	满足条件A的位置
左边界二分	条件A：nums[mid] ≥ target	满足条件A的第一个位置
右边界二分	条件A：nums[mid] ≤ target	满足条件A的最后一个位置

所有二分变形题，本质都是“确定条件A”和“确定目标位置（第一个/最后一个满足A的位置）”。比如：

• LeetCode 35（搜索插入位置）：条件A是nums[mid] ≥ target，目标是第一个满足A的位置；
• LeetCode 69（x的平方根）：条件A是mid² ≤ x，目标是最后一个满足A的位置；
• 甚至“找数组中唯一不重复的元素”“旋转数组的最小元素”等题，本质也是通过定义新的“条件A”，用二分缩小范围。

总结：从“会用”到“活用”的3个步骤

通过这篇博客，我们从“朴素二分的局限”出发，拆解了左右边界模板的逻辑，并用实战题验证了模板的通用性。最后，给大家总结一套“从会用到活用”的学习路径：

1. 抓核心，记模板：先理解左右边界模板的“循环条件、mid取整、缩范围逻辑”，重点记住“左边界找第一个≥target，右边界找最后一个≤target”；
2. 辨题型，定条件：遇到新题时，先思考“这道题要找的是‘第一个满足某条件的位置’还是‘最后一个满足某条件的位置’”，确定“条件A”是什么（比如LeetCode 69的条件A是mid² ≤x）；
3. 勤调试，避陷阱：写代码时，先测试小规模数组和边缘场景（空数组、target在首尾、target不存在），手动模拟循环过程，避免死循环和越界。

二分查找的难点不在代码本身，而在“如何将问题转化为边界查找”。只要掌握了“二段性”这个核心，不管是LeetCode的中等题，还是面试中的变形题，都能游刃有余。下次再遇到二分题，别慌，先问自己：“我要找的是左边界还是右边界？条件A是什么？”——想清楚这两个问题，代码自然就出来了！

“喏，Doro给你一朵小花🌸奖励看到这里的你，这篇二分查找的拆解有没有把你心里的‘小疑惑’全捋顺呀？要是你觉得这篇博客把单调性、二段性这些‘小细节’讲得明明白白，就给个点赞鼓励一下嘛~ 要是怕以后找不到这么贴心的讲解，可得赶紧收藏起来！不然下次遇到二分问题，Doro怕你会像Doro一样因为找不到 Orange 时那样‘委屈巴巴’哦~ Doro 知道这个博主后面还会扒更多算法‘小秘密’，关注他，带你从‘看着会’到‘写得对’，再也不被二分的细节‘背刺’啦~