34. 在排序数组中查找元素的第一个和最后一个位置 Medium
给你一个按照非递减顺序排列的整数数组 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]
解题思路
输入： 一个递增的有序数组 nums，一个目标值 target
输出： 返回目标值在数组中的起始位置和结束位置，若不存在则返回 [-1, -1]。
本题属于边界查找类问题，关键在于利用二分查找精确定位目标值的左右边界。
我们定义一个辅助函数 lower_bound(nums, target)，用于查找第一个大于等于 target 的下标（即左边界位置）。
具体步骤如下：
查找左边界：
调用 lower_bound(nums, target)，获得目标值的起始位置 start。
若 start == nums.length（越界）或 nums[start] !== target，说明目标值不存在，直接返回 [-1, -1]。
查找右边界：
调用 lower_bound(nums, target + 1)，找到第一个大于目标值的位置，减一即可得到目标值的结束位置 end。
返回结果：
返回 [start, end] 即为目标值的起始与结束位置。
代码实现
python
# 查找第一个大于等于 target 的下标（即左边界）
def lower_bound(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
# 如果中间值比目标小，说明目标在右半部分
left = mid + 1
else:
# 如果中间值大于等于目标，有可能是答案，缩小右边界
right = mid - 1
# 最终 left 指向第一个 >= target 的位置
return left
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# 查找 target 的第一个出现位置
start = lower_bound(nums, target)
# 如果 start 越界或对应位置不是 target，说明 target 不存在
if start == len(nums) or nums[start] != target:
return [-1, -1]
# 查找 target + 1 的第一个位置，减一得到最后一个 target 的位置
end = lower_bound(nums, target + 1) - 1
return [start, end]javascript
const searchRange = function(nums, target) {
/**
* 二分查找：返回第一个大于等于 target 的下标
* 如果目标存在，这是它的起始位置
*/
function lowerBound(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] >= target) {
// 当前值 ≥ target，可能是答案，继续往左找更小的
right = mid - 1;
} else {
// 当前值 < target，答案一定在右边
left = mid + 1;
}
}
// 最终 left 指向第一个 ≥ target 的下标
return left;
}
const start = lowerBound(nums, target);
// 如果越界，或 nums[start] 不等于目标值，说明不存在
if (start === nums.length || nums[start] !== target) {
return [-1, -1];
}
// 查找第一个 ≥ target + 1 的位置，减 1 得到最后一个 target 出现的位置
const end = lowerBound(nums, target + 1) - 1;
return [start, end];
};复杂度分析
时间复杂度：O(log n)
空间复杂度：O(1)