34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
一、核心思想总结 来源：灵茶山艾府
有序数组中目标值的区间
[start, end] 满足两个特征：start是数组中第一个 ≥ target 的元素下标（目标值的起始位置）；end是数组中第一个 ≥ target+1 的元素下标 - 1（目标值的结束位置）；- 若
start超出数组范围，或nums[start] ≠ target，说明目标值不存在，返回[-1,-1]。
简单理解：把目标值的区间看作「夹在 target 和 target+1 之间」，用两次二分找到这两个边界，就能快速确定目标值的起止位置。
lowbound 方法的核心逻辑：
- 循环中不断缩小范围，最终
left会停在「第一个大于等于 target 的元素下标」； - 特殊情况：
- 若 target 比所有元素大 →
left = nums.length（超出数组范围）； - 若 target 比所有元素小 →
left = 0； - 若数组为空 →
left = 0（循环不执行，直接返回）。
- 若 target 比所有元素大 →
【背】
right = mid-1 不可以换成break。通过right左移，nums[mid]在变化 带动left变化移动至第一个target
while(left<=right){int mid = (right-left)/2+left;if(nums[mid] < target) left = mid+1;else right = mid-1;}
【完整代码】
class Solution {/*** 在有序整数数组中查找目标值的第一个和最后一个位置* @return 目标值的起始和结束下标，不存在则返回 [-1,-1]*/public int[] searchRange(int[] nums, int target) {// 1. 找第一个 >= target 的元素下标（目标值的起始位置）int start = lowbound(nums, target);// 2. 找第一个 >= target+1 的元素下标，减1即为目标值的结束位置int end = lowbound(nums, target + 1) - 1;// 3. 判断目标值是否不存在：// - 情况1：start == nums.length → target比所有元素都大（下标越界）// - 情况2：nums[start] != target → 数组中无target（start指向的元素不是target）// 注意：必须先判断start是否越界，再访问nums[start]，避免数组下标越界异常if (start == nums.length || nums[start] != target) {return new int[]{-1, -1};}// 4. 目标值存在，返回起止下标return new int[]{start, end};}//二分查找：找数组中第一个 >= target 的元素下标（下界查找）// return 第一个 >= target 的元素下标；若所有元素都 < target，返回nums.lengthpublic int lowbound(int[] nums, int target) {// 左边界：初始化为数组第一个元素的下标int left = 0;// 右边界：初始化为数组最后一个元素的下标int right = nums.length - 1;// 二分查找核心循环：缩小查找范围，直到left > rightwhile (left <= right) {// 计算中间下标：避免 (left + right) 整数溢出，等价于 (left + right) / 2int mid = (right - left) / 2 + left;if (nums[mid] < target) {// 中间值 < 目标值 → 下界在右半区，左边界右移left = mid + 1;} else {// 中间值 >= 目标值 → 下界在左半区（包括mid），右边界左移right = mid - 1;}}// 循环结束时，left 即为第一个 >= target 的元素下标return left;} }
【灵神NB】
end = lowbound(nums, target + 1) - 1 这也太巧妙了