二分查找(2)

一.题目

34. 在排序数组中查找元素的第一个和最后一个位置 – 力扣（LeetCode）

二.思路

        2.1 引入

        在上节课中，我们学习了普通二分查找，其中求中点的方式有两种：一种是不加1的写法 mid = left + (right – left) / 2，另一种是加1的写法 mid = left + (right – left + 1) / 2。那么，这两种写法的区别是什么？ 它们在数组长度为偶数时体现——不加1时中点会偏向左边，而加1时中点会偏向右边。

        正是这个细微的差别，衍生出了两种不同的二分查找变体：寻找左边界和寻找右边界。接下来，我将以左边界为例，为大家详细讲解。

        2.2 左边界讲解

一、什么是左边界问题？

        在一个有序数组中，如果存在重复元素，我们可能需要找到第一个等于目标值的位置，这就是左边界。普通二分查找只要找到一个目标就返回，不关心它在重复元素中的位置；而左边界要求在多个相同目标中返回最左边的下标。

二、整体思想

        左边界二分查找依然利用数组的有序性（二分性），每次将搜索区间缩小一半。但与普通二分不同，它的区间缩进规则需要保证最终收敛到第一个等于目标的位置。核心在于：当中间值等于目标时，不能直接返回，而要继续向左搜索，因为左边可能还有相同值。

三、循环条件

        采用 while (left < right) 作为循环条件。为什么不是 left <= right？ 因为当 left == right 时，区间内只剩下一个元素，此时无需再二分，可以直接判断这个元素是否为目标。使用 < 可以避免在区间缩小时陷入死循环，并且在循环结束后自然得到唯一候选位置。

四、计算中点

        中点计算公式为：mid = left + (right – left) / 2，即向下取整（不加1）。 在数组长度为偶数时，中点会偏向左边。这种取法对于左边界查找至关重要：它确保当 left 和 right 相邻时，中点就是 left，从而避免陷入死循环，并与后续缩进规则配合，使区间稳定向左侧收缩。

五、区间缩进规则

        在循环中，比较 nums[mid] 与目标值 target，根据结果更新指针：

        为什么这里用 right = mid 而不是 mid – 1？         因为当 nums[mid] == target 时，mid 有可能是左边界，必须保留；当 nums[mid] > target 时，目标在左边，但 mid 本身不可能，不过为了统一逻辑，采用 right = mid 可以保证区间正确收缩，并且不会错过可能的左边界。

六、循环结束后的处理

        当 while (left < right) 结束时，必有 left == right，此时区间仅剩一个元素。我们需要判断这个元素是否等于目标：

• 如果 nums[left] == target，则 left 就是左边界，返回该下标。

• 否则，说明数组中不存在目标，返回 -1。

七、关键点总结

• 中点取法必须向下取整（不加1），这是左边界查找的精髓，避免死循环。

• 循环条件用 left < right，保证最后只剩一个元素时退出，并统一判断。

• 缩进规则：当 nums[mid] < target 时 left = mid + 1；否则 right = mid。这种规则确保区间始终向左侧收敛。

• 最终判断不可省略，因为循环结束时 left 指向的元素未必是目标。

        2.3 右边界讲解

一、什么是右边界问题？

        在一个有序数组中，如果存在重复元素，有时我们需要找到最后一个等于目标值的位置，这就是右边界。与左边界对称，右边界要求在多个相同目标中返回最右边的下标。

二、整体思想

        右边界二分查找依然利用数组的有序性（二分性），每次将搜索区间缩小一半。其核心在于：当中间值等于目标时，不能直接返回，而要继续向右搜索，因为右边可能还有相同值。因此，区间缩进规则需要保证最终收敛到最后一个等于目标的位置。

三、循环条件

        采用 while (left < right) 作为循环条件。为什么不是 left <= right？ 因为当 left == right 时，区间内只剩下一个元素，此时无需再二分，可以直接判断这个元素是否为目标。使用 < 可以避免在区间缩小时陷入死循环，并且在循环结束后自然得到唯一候选位置。

四、计算中点

        中点计算公式为：mid = left + (right – left + 1) / 2，即向上取整（加1）。 在数组长度为偶数时，中点会偏向右边。这种取法对于右边界查找至关重要：它确保当 left 和 right 相邻时，中点就是 right，从而避免陷入死循环，并与后续缩进规则配合，使区间稳定向右侧收缩。

五、区间缩进规则

        在循环中，比较 nums[mid] 与目标值 target，根据结果更新指针：

        为什么这里用 left = mid 而不是 mid + 1？         因为当 nums[mid] == target 时，mid 有可能是右边界，必须保留；当 nums[mid] < target 时，目标在右边，但 mid 本身不可能，不过为了统一逻辑，采用 left = mid 可以保证区间正确收缩，并且不会错过可能的右边界。

六、循环结束后的处理

        当 while (left < right) 结束时，必有 left == right，此时区间仅剩一个元素。我们需要判断这个元素是否等于目标：

• 如果 nums[left] == target，则 left 就是右边界，返回该下标。

• 否则，说明数组中不存在目标，返回 -1。

七、关键点总结

• 中点取法必须向上取整（加1），这是右边界查找的精髓，避免死循环。

• 循环条件用 left < right，保证最后只剩一个元素时退出，并统一判断。

• 缩进规则：当 nums[mid] > target 时 right = mid – 1；否则 left = mid。这种规则确保区间始终向右侧收敛。

• 最终判断不可省略，因为循环结束时 left 指向的元素未必是目标

三.代码演示

class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target)
{
vector<int>v;
int n = nums.size();
//为空，那么访问数组会越界
if(n == 0)
return {-1,-1};
int left1 = 0;
int right1 = n-1;
//左边界
while(left1 < right1)
{
//求中点
int mid = left1 + (right1 – left1)/2;
if(nums[mid] < target)
left1 = mid + 1;
else
{
right1 = mid;
}
}
if(nums[left1] == target)
v.push_back(left1);
int left2 = 0;
int right2 = n-1;
//右边界
while(left2 < right2)
{
//求中点
int mid = left2 + (right2 – left2 + 1)/2;
if(nums[mid] > target)
right2 = mid – 1;
else
{
left2 = mid;
}
}
if(nums[left2] == target)
v.push_back(left2);

if(v.size() != 2)
return {-1,-1};
return v;
}

};