二分查找(在排序数组查找元素)(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] targetmid本身可能就是左边界但左边可能还有相同值因此不能排除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] targetmid本身可能就是右边界但右边可能还有相同值因此不能排除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: vectorint searchRange(vectorint nums, int target) { vectorintv; 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; } };