文章内容
模板
lowerBound（左边界，第一个 >= target）：
int lowerBound(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l < r) { int mid = l + (r - l) / 2; // 不 +1，向左收敛 if (nums[mid] >= target) r = mid; else l = mid + 1; } return l;}upperBound（右边界，最后一个 <= target）：
int upperBound(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l < r) { int mid = l + (r - l + 1) / 2; // 必须 +1，否则死循环 if (nums[mid] <= target) l = mid; else r = mid - 1; } return l;}一、题目解析
给一个非递减数组 nums 和一个目标值 target，找出 target 在数组中的起始位置和结束位置。如果不存在，返回 [-1, -1]。要求 O(log n) 时间。
示例：
输入: nums = [5,7,7,8,8,10], target = 8输出: [3,4] 输入: nums = [5,7,7,8,8,10], target = 6输出: [-1,-1]O(log n) 意味着必须用二分。但标准二分只能找到一个位置——当数组里有重复元素时，找到的可能是中间的某一个。这道题要的是第一个和最后一个。
思路：写两个二分变体，一个向左收敛找左边界，一个向右收敛找右边界。
二、算法原理
2.1 lowerBound —— 找第一个位置
目标：在有序数组里，找到第一个 >= target 的位置。
核心在于 mid 的计算和区间的收缩方向。mid = l + (r - l) / 2，不 +1，mid 倾向于靠左。
- 当
nums[mid] >= target：mid本身可能是答案 →r = mid，区间向左收缩。 - 当
nums[mid] < target：mid及左边都不可能是答案 →l = mid + 1。
区间不断向左挤压，最终 l == r 时退出，l 就是第一个满足 >= target 的位置。
2.2 upperBound —— 找最后一个位置
目标：找到最后一个 <= target 的位置。
关键差异：mid = l + (r - l + 1) / 2，这里必须 +1。
为什么+1？
当区间只剩两个元素 [l, l+1] 时，如果不 +1，mid = l，而 l = mid 不会改变 l，死循环。+1 让 mid 靠右，确保每次迭代区间都真实缩小。
- 当
nums[mid] <= target：mid可能是答案 →l = mid，区间向右收缩。 - 当
nums[mid] > target：mid及右边都不可能是答案 →r = mid - 1。
2.3 两个函数对比
| lowerBound | upperBound | |
|---|---|---|
| mid 计算 | l + (r - l) / 2 |
l + (r - l + 1) / 2 |
| 满足条件时 | r = mid（向左收） |
l = mid（向右收） |
| 不满足时 | l = mid + 1 |
r = mid - 1 |
| 找到的位置 | 第一个 >= target | 最后一个 <= target |
三、图解过程
以 nums = [5,7,7,8,8,10], target = 8 为例。
3.1 lowerBound 执行过程
初始区间 [0, 5]，mid = (0+5)/2 = 2，nums[2]=7 < 8，不满足 → l = 3。区间缩到 [3, 5]。
mid = (3+5)/2 = 4，nums[4]=8 >= 8，满足 → r = 4。区间缩到 [3, 4]。
mid = (3+4)/2 = 3，nums[3]=8 >= 8，满足 → r = 3。l == r == 3，循环结束。
返回 3，恰好是第一个 8 的位置。
3.2 upperBound 执行过程
初始区间 [0, 5]，mid = (0+5+1)/2 = 3，nums[3]=8 <= 8，满足 → l = 3。区间缩到 [3, 5]。
mid = (3+5+1)/2 = 4，nums[4]=8 <= 8，满足 → l = 4。区间缩到 [4, 5]。
mid = (4+5+1)/2 = 5，nums[5]=10 > 8，不满足 → r = 4。l == r == 4，循环结束。
返回 4，恰好是最后一个 8 的位置。
3.3 searchRange 组合
lowerBound 返回 3，检查 nums[3] == 8，确实等于 target。upperBound 返回 4。答案是 [3, 4]。
如果 target 不存在——比如找 6——lowerBound 会返回第一个 >= 6 的位置（即 nums[1]=7），但 nums[1] != 6，触发 return [-1, -1]。
四、代码实现
class Solution { // lowerBound：找第一个 >= target 的位置 // mid 不 +1，向左收敛；循环不变式：答案在 [l, r] 内 int lowerBound(int[] nums, int target) { int l = 0; int r = nums.length - 1; while (l < r) { int mid = l + (r - l) / 2; // 偏左，不 +1 if (nums[mid] >= target) { r = mid; // mid 可能就是答案 } else { l = mid + 1; // mid 太小，跳过 } } return l; } // upperBound：找最后一个 <= target 的位置 // mid 必须 +1，否则区间 [l, l+1] 时 mid = l，l = mid 导致死循环 int upperBound(int[] nums, int target) { int l = 0; int r = nums.length - 1; while (l < r) { int mid = l + (r - l + 1) / 2; // 偏右，必须 +1 if (nums[mid] <= target) { l = mid; // mid 可能就是答案 } else { r = mid - 1; // mid 太大，跳过 } } return l; } public int[] searchRange(int[] nums, int target) { // 先找左边界 int left = lowerBound(nums, target); // 左边界越界或对应元素不等于 target，说明 target 不存在 // 空数组时 left == 0 == nums.length，也会被此条件捕获 if (left == nums.length || nums[left] != target) { return new int[]{-1, -1}; } // target 存在，再找右边界 int right = upperBound(nums, target); return new int[]{left, right}; }}总结：
lowerBound的mid不 +1。因为收缩用的是r = mid，mid偏左不影响收敛。upperBound的mid必须 +1。因为收缩用的是l = mid，不 +1 在[l, l+1]区间会死循环（mid永远等于l，而l = mid不改变l）。
本文由 AgentPlanFlow 生成