题目描述
给定非递减排序的整数数组 nums 和目标值 target，需找到 target 在数组中的第一个位置和最后一个位置；若不存在则返回 [-1, -1]，要求时间复杂度为 O(log n)。
核心要求：依托排序数组特性，用二分查找高效定位边界，拒绝线性遍历。
核心思路：用'找第一个≥目标值'的二分模板统一边界逻辑
二分查找的核心是在有序序列中定位满足条件的第一个位置。我们只需实现一个通用二分模板 ——查找数组中第一个大于等于目标值的索引（方法名统一为 binarySearch），即可统一解决本题的两个边界问题：
第一个位置：直接调用
binarySearch查找target，得到第一个≥target的索引；若索引越界或对应值不等于target，说明target不存在。 最后一个位置：等价于调用binarySearch查找第一个**≥target+1** 的索引，再将结果减 1。原因是：非递减数组中，target+1的首个出现位置的前一位，就是target的最后一次出现位置。
上述最后一个位置的转化可以参考以下表格：
| 你想找的 | 等价问题（转换思路） | 调用 binarySearch | 返回的 idx 含义 | 最终答案（位置或值） | 举例 (nums=[1,3,3,5,7]) |
|---|---|---|---|---|---|
第一个 >= x | 原问题 | binarySearch(nums, x) | 第一个 >= x 的位置 | idx（若越界则无解） | x=3 → idx=1（值 3） |
第一个 > x | 第一个 >= (x+1) | binarySearch(nums, x+1) | 第一个 >= x+1 的位置 | idx（若越界则无解） | x=3 → idx=3（值 5） |
最后一个 < x | 第一个 >= x 的左边 | binarySearch(nums, x) | 第一个 >= x 的位置 | idx - 1（若 idx=0 则无解） | x=3 → idx=1，答案 0（值 1） |
最后一个 <= x | 第一个 > x 的左边 或 第一个 >= x+1 的左边 | binarySearch(nums, x+1) | 第一个 > x 的位置 | idx - 1（若 idx=0 则无解） | x=3 → idx=3，答案 2（值 3） |
代码实现
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = binarySearch(nums, target); // 边界校验：target 不存在的情况
if (start == nums.length || nums[start] != target) {
return new int[]{-1, -1};
}
// 推导最后一个位置
int end = binarySearch(nums, target + 1) - 1;
return new int[]{start, end};
}
/**
* 通用二分模板：返回数组中第一个大于等于 target 的索引
* @param nums 非递减排序的数组
* @param target 目标值
* @return 首个≥target 的索引；若所有元素都小于 target，返回数组长度
*/
private int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
// 避免(left + right) 溢出，等价于(left + right) / 2
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 目标值在右区间，左边界右移
left = mid + 1;
} else {
// 目标值在左区间，右边界左移
right = mid - 1;
}
}
return left;
}
}
关键解析
binarySearch模板：严格实现'找第一个≥目标值'的逻辑，循环结束后left即为目标索引，天然处理'所有元素小于目标值'的越界场景。 存在性校验：通过start的越界判断和值匹配，直接筛除target不存在的情况。 最后位置推导：借助binarySearch(nums, target + 1)的查找结果，一步计算出target的最后位置，无需额外二分。
