一、题目描述
给你一个按照非递减顺序排列的整数数组nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值target，返回[-1, -1]。
你必须设计并实现时间复杂度为O(log n)的算法解决此问题。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]示例 3:
输入: nums = [], target = 0
输出: [-1,-1]二、解题思路
- 题目明确要求时间复杂度为
O(log n)，暴力遍历（O(n)）不符合要求，必须使用二分查找。 - 核心需求拆解：找到目标值的左边界（第一个等于target的位置）和右边界（最后一个等于target的位置）。
- 优化思路：复用同一个“找下界”的二分函数，避免写两套逻辑：
1. 左边界：直接调用lowBound(nums, target)，得到第一个大于等于target的索引；
2. 右边界：调用lowBound(nums, target + 1)得到第一个大于等于target+1的索引，再减1，即为最后一个等于target的索引；
3. 先判断左边界是否有效（是否存在target），不存在则直接返回[-1,-1]。
三、代码实现（Java）
class Solution {
public int[] searchRange(int[] nums, int target) {
// 1. 找目标值的左边界（第一个等于target的位置）
int start = lowBound(nums, target);
// 2. 判断目标值是否存在：左边界超出数组或对应元素不等于target，说明不存在
if (start == nums.length || nums[start] != target) {
return new int[]{-1, -1};
}
// 3. 找右边界：找target+1的下界，再减1，即为最后一个等于target的位置
int end = lowBound(nums, target + 1) - 1;
return new int[]{start, end};
}
/**
* 找数组中第一个大于等于target的元素的索引（下界函数）
* @param nums 非递减排序数组
* @param target 目标值
* @return 第一个大于等于target的索引，不存在则返回nums.length
*/
public int lowBound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid = 0;
// 闭区间二分查找，保证遍历所有元素
while (left <= right) {
// 计算中间位置，避免low + high直接相加导致int溢出
mid = left + (right - left) / 2;
if (nums[mid] >= target) {
// mid值大于等于target，左边界在左侧（含mid），更新右边界
right = mid - 1;
} else {
// mid值小于target，左边界在右侧（不含mid），更新左边界
left = mid + 1;
}
}
// 循环结束时left即为第一个大于等于target的位置
return left;
}
}四、核心笔记 & 易错点解析
1. 二分查找中“等于”情况的合并逻辑
- 正常二分查找中，若nums[mid] > target，需要向左查找（right = mid - 1）；
- 在找下界（第一个大于等于target的位置）时，nums[mid] == target也需要向左查找（因为左侧可能存在更小的索引等于target），因此将==与>的情况合并处理，统一更新right = mid - 1；
- 若要找上界（最后一个等于target的位置），则nums[mid] == target需要向右查找，此时==应与<的情况合并，更新left = mid + 1；
- 无需死记硬背“等于和谁合并”，只需根据找上下界的需求，确定==时该往哪个方向缩小区间，再合并即可。
2. 目标值不存在的三种情况分析
调用lowBound函数后，若目标值不在数组中，会出现三种情况：
- 数组所有元素都小于target：此时left = nums.length（超出数组范围），right = nums.length - 1，需通过start == nums.length判断不存在；
- 数组所有元素都大于target：此时left = 0，但nums[left] != target，需通过nums[start] != target判断不存在；
- 数组中部分元素小于target、部分大于target：此时right是小于target的最大值的索引，left是大于target的最小值的索引，同样通过nums[start] != target判断不存在；
因此，调用lowBound后，必须加上start == nums.length || nums[start] != target的判断，才能确定target是否存在。
3. 循环结束的边界特性
由于while (left <= right)的循环条件，无论==与谁合并在一起，循环结束时一定满足right < left，且right + 1 == left：
- 若target存在于数组中，left是目标值的下界，right是小于target的最大元素的索引；
- 若target不存在，left是target应该插入的位置，right是小于target的最大元素的索引；
这个特性是后续计算右边界（lowBound(nums, target + 1) - 1）的核心依据。
五、复杂度分析
-时间复杂度：O(log n)，两次调用lowBound函数，每次都是二分查找，时间复杂度为O(log n)，两次调用仍为O(log n)，符合题目要求。
-空间复杂度：O(1)，仅使用了常数级别的额外变量，没有使用额外的辅助空间。
六、总结
- 这道题的核心是利用“找下界”的二分函数，同时解决目标值左右边界的查找问题，避免了写两套二分逻辑，代码更简洁易维护。
- 关键在于理解二分查找中==情况的合并逻辑，以及循环结束后left和right的边界特性。
- 必须先判断目标值是否存在，再计算右边界，避免数组越界或返回错误结果。
