二分查找(在排序数组查找元素)(2)
https://blog.csdn.net/2601_95366422/article/details/158657963
上节课链接
一.题目
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，根据结果更新指针：
当
nums[mid] < target时
说明目标值一定在mid的右侧，且mid及其左边所有元素都小于目标，因此它们都不可能是左边界。所以将左指针移动到mid + 1，即left = mid + 1，舍弃左半区间。当
nums[mid] >= target时
这里包含了两种情况：nums[mid] > target或nums[mid] == target。如果
nums[mid] > target，目标在左边，左边界肯定在mid左侧（可能等于某个更小的位置）。如果
nums[mid] == target，mid本身可能就是左边界，但左边可能还有相同值，因此不能排除mid，需要继续向左搜索。
无论哪种情况，左边界都在mid及左侧区间内，因此将右指针移动到mid，即right = mid，保留mid在搜索区间中。
为什么这里用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，根据结果更新指针：
当
nums[mid] > target时
说明目标值一定在mid的左侧，且mid及其右边所有元素都大于目标，因此它们都不可能是右边界。所以将右指针移动到mid - 1，即right = mid - 1，舍弃右半区间。当
nums[mid] <= target时
这里包含了两种情况：nums[mid] < target或nums[mid] == target。如果
nums[mid] < target，目标在右边，右边界肯定在mid右侧（可能等于某个更大的位置）。如果
nums[mid] == target，mid本身可能就是右边界，但右边可能还有相同值，因此不能排除mid，需要继续向右搜索。
无论哪种情况，右边界都在mid及右侧区间内，因此将左指针移动到mid，即left = mid，保留mid在搜索区间中。
为什么这里用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; } };