LeetCode - 34. 在排序数组中查找元素的第一个和最后一个位置

题目

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

思路

查找左边界

初始化 left = 0, right = nums.size() - 1

当 left < right 时循环：

• 计算中点 mid = left + (right - left) / 2

• 如果 nums[mid] < target，目标在右侧，left = mid + 1

• 否则，目标在左侧或当前位置，right = mid

循环结束后，left == right，检查 nums[left] 是否等于 target

查找右边界

初始化 left = 0, right = nums.size() - 1

当 left < right 时循环：

• 计算中点 mid = left + (right - left + 1) / 2 （向上取整）

• 如果 nums[mid] > target，目标在左侧，right = mid - 1

• 否则，目标在右侧或当前位置，left = mid

循环结束后，left == right，检查 nums[left] 是否等于 target

图解过程

以数组 [5, 7, 7, 8, 8, 10]，目标值 target = 8 为例：

查找左边界

初始状态：

索引:  0  1  2  3  4  5
数组: [5, 7, 7, 8, 8, 10]↑           ↑left        right

 第一次迭代：

• mid = 0 + (5-0)/2 = 2

• nums[mid] = 7 < 8，目标在右侧

• left = mid + 1 = 3

索引:  0  1  2  3  4  5
数组: [5, 7, 7, 8, 8, 10]↑     ↑left  right

 第二次迭代：

• mid = 3 + (5-3)/2 = 4

• nums[mid] = 8 == 8，目标可能在左侧

• right = mid = 4

索引:  0  1  2  3  4  5
数组: [5, 7, 7, 8, 8, 10]↑  ↑left right

 第三次迭代：

• mid = 3 + (4-3)/2 = 3

• nums[mid] = 8 == 8，目标可能在左侧

• right = mid = 3

索引:  0  1  2  3  4  5
数组: [5, 7, 7, 8, 8, 10]↑leftright

 循环结束：

• left == right = 3，循环结束

• nums[left] = 8 == target，找到左边界 begin = 3

查找右边界

初始状态：

索引:  0  1  2  3  4  5
数组: [5, 7, 7, 8, 8, 10]↑           ↑left        right

 第一次迭代：

• mid = 0 + (5-0+1)/2 = 3 （向上取整）

• nums[mid] = 8 == 8，目标可能在右侧

• left = mid = 3

索引:  0  1  2  3  4  5
数组: [5, 7, 7, 8, 8, 10]↑     ↑left  right

 第二次迭代：

• mid = 3 + (5-3+1)/2 = 5 （向上取整）

• nums[mid] = 10 > 8，目标在左侧

• right = mid - 1 = 4

索引:  0  1  2  3  4  5
数组: [5, 7, 7, 8, 8, 10]↑  ↑left right

 第三次迭代：

• mid = 3 + (4-3+1)/2 = 4 （向上取整）

• nums[mid] = 8 == 8，目标可能在右侧

• left = mid = 4

索引:  0  1  2  3  4  5
数组: [5, 7, 7, 8, 8, 10]↑leftright

循环结束：

• left == right = 4，循环结束

• nums[left] = 8 == target，找到右边界 end = 4

最终结果

返回 [begin, end] = [3, 4]，表示目标值 8 的第一个位置是索引 3，最后一个位置是索引 4。

关键点

• 使用 left < right 作为循环条件，确保循环结束时 left == right
• 查找左边界时使用向下取整计算 mid，更新方式为 right = mid
• 查找右边界时使用向上取整计算 mid，更新方式为 left = mid
• 循环结束后检查 nums[left] 是否等于目标值

读者可能会出现的错误写法

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.empty()){return {-1,-1};}int left = 0;int right = nums.size()-1;int begin = -1;int end =-1;while(left <= right){int mid = left + (right-left)/2;if(nums[mid]<target){left = mid + 1;}else{right = mid-1;}}if(nums[left] == target){begin = left;}left = 0;right = nums.size()-1;while(left <= right){int mid = left + (right-left)/2;if(nums[mid] > target){right = mid-1;}else{left = mid+1;}}if(nums[right] == target){end = right;}return {begin,end};}
};

在查找左边界的时候，right = mid而不是right = mid-1;在查找右边界的时候，left = mid而不是left = mid+1,并且left<right 而不是left<=right,并且当left=mid的条件下，mid = left + (right-left+1)/2,而不是mid = left + (right-left)/2

为什么要用right = mid而不是right = mid - 1？

• 如果nums[mid] == target，mid可能就是我们要找的左端点，或者左端点在mid左侧

• 如果我们使用right = mid - 1，就可能错过正确答案

• 使用right = mid可以保留mid作为可能的答案，同时继续向左搜索

为什么我们使用right = mid - 1，就可能错过正确答案

假设数组中有多个相同的目标值，例如[1, 3, 3, 3, 5]，目标值target = 3。 

当我们找到一个nums[mid] == target时（例如中间的那个3），我们不知道这是不是第一个出现的3。有两种可能：

• 当前找到的这个3就是第一个3
• 在mid左侧还有其他的3

使用right = mid - 1的问题：

如果当前找到的nums[mid] == target恰好是第一个出现的目标值，那么使用right = mid - 1会将搜索范围缩小到mid左侧，完全排除了mid这个位置。

具体例子：

• 数组[1, 2, 3, 4, 5]，target = 3

• 初始：left = 0, right = 4

• 第一次迭代：mid = 2, nums[mid] = 3 == target

• 如果使用right = mid - 1，区间变为[0, 1]

• 但索引2处的元素（值为3）是我们要找的答案！我们已经排除了它

• 后续迭代会在[0, 1]范围内搜索，但这个范围内没有值为3的元素

• 最终会得出错误结论，认为数组中不存在目标值

使用right = mid的优势：

当nums[mid] == target时，使用right = mid：

• 将右边界移动到mid（而不是mid-1）

• 保留了mid作为可能的答案

• 同时继续在左侧搜索是否有更早出现的目标值

这样，即使当前的mid就是第一个目标值，我们也不会错过它，因为：

• 如果左侧没有其他目标值，循环最终会收敛到这个位置

• 如果左侧有目标值，我们会找到那个更早的位置

总结：使用right = mid - 1在找到目标值时会完全排除当前位置，如果当前位置恰好是第一个目标值，就会错过正确答案。而right = mid保留了当前位置作为候选答案，同时继续向左搜索可能存在的更早出现的目标值。

为啥查找左端点的mid算法和查找右端点的mid算法不一样

考虑当搜索区间缩小到只有两个元素时，例如 [3, 4]：

• left = 3, right = 4
• mid = 3 + (4-3)/2 = 3（向下取整）
• 如果 nums[mid] <= target，执行 left = mid = 3
• 新的搜索区间仍然是 [3, 4]
• 下一次迭代，mid仍然是3
• 如果 nums[mid] <= target，又执行 left = mid = 3
• 搜索区间永远是 [3, 4]，无法进一步缩小，陷入死循环

使用向上取整的解决方案

使用向上取整 mid = left + (right - left + 1) / 2 可以解决这个问题：

• left = 3, right = 4
• mid = 3 + (4-3+1)/2 = 4（向上取整）
• 如果 nums[mid] > target，执行 right = mid - 1 = 3
• 搜索区间变为 [3, 3]，循环结束

或者，如果 nums[mid] <= target，执行 left = mid = 4，区间变为 [4, 4]，循环也会结束。

为什么查找左端点不需要向上取整

关键在于更新策略的不同：

查找左端点时：

• 当 nums[mid] < target 时，使用 left = mid + 1

• 这个 +1 确保了即使 mid = left，区间也会缩小

查找右端点时：

• 当 nums[mid] <= target 时，使用 left = mid（没有 +1）

• 如果 mid = left，区间不会缩小，导致死循环

总结

• 查找左端点时，即使使用向下取整，也不会导致死循环，因为：

• 当 nums[mid] < target 时，left = mid + 1 会缩小区间

• 当 nums[mid] >= target 时，right = mid 会缩小区间（因为 mid ≤ right）

• 查找右端点时，使用向下取整可能导致死循环，因为：

• 当 nums[mid] <= target 且 mid = left 时，left = mid 不会缩小区间

当使用right = mid和left = mid这种更新方式时，循环条件应该是while(left < right)而不是while(left <= right)。为啥呀

原因如下：

主要原因：避免死循环

如果使用while(left <= right)作为循环条件，当left == right时循环仍会继续执行：

当left == right时，无论使用什么mid计算方式，都会得到mid == left == right

此时：

• 如果执行right = mid，结果是right = left，区间不变

• 如果执行left = mid，结果是left = right，区间不变

下一次循环，条件left <= right仍然满足（因为left == right）

区间没有缩小，算法陷入死循环

具体例子

假设数组[1, 3, 5]，当搜索区间缩小到[1, 1]（即left = right = 1）：

如果使用while(left <= right)：

• mid = 1

• 如果执行right = mid，区间仍为[1, 1]

• 如果执行left = mid，区间仍为[1, 1]

• 下一次循环，条件仍然满足，陷入死循环

正确的写法

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.empty()){return {-1,-1};}int left = 0;int right = nums.size()-1;int begin = -1;int end =-1;while(left < right){int mid = left + (right-left)/2;if(nums[mid]<target){left = mid + 1;}else{right = mid;}}if(nums[left] == target){begin = left;}left = 0;right = nums.size()-1;while(left < right){int mid = left + (right-left + 1)/2;if(nums[mid] > target){right = mid-1;}else{left = mid;}}if(nums[right] == target){end = right;}return {begin,end};}
};