难度: 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]
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums 是一个非递减数组-109 <= target <= 109运行时间: 48 ms
内存: 15.5 MB
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
ans = [-1, -1]
if len(nums) == 0:
return ans
l = 0
r = len(nums) - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] >= target:
r = mid
else:
l = mid + 1
if nums[l] == target:
ans[0] = l
l = 0
r = len(nums) - 1
while l < r:
mid = l + (r - l + 1) // 2
if nums[mid] <= target:
l = mid
else:
r = mid - 1
if nums[l] == target:
ans[1] = l
return ans
这个题解使用二分查找的思路来寻找目标值的开始位置和结束位置。首先用一次二分查找寻找目标值的左边界，即第一个大于等于目标值的位置。如果找到目标值，则再用一次二分查找寻找目标值的右边界，即最后一个小于等于目标值的位置。最后返回找到的左右边界作为结果。如果没有找到目标值，则返回[-1, -1]。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
ans = [-1, -1]
if len(nums) == 0:
return ans
# 二分查找目标值的左边界
l = 0
r = len(nums) - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] >= target:
r = mid
else:
l = mid + 1
# 如果找到目标值，则继续查找右边界
if nums[l] == target:
ans[0] = l
l = 0
r = len(nums) - 1
while l < r:
mid = l + (r - l + 1) // 2
if nums[mid] <= target:
l = mid
else:
r = mid - 1
if nums[l] == target:
ans[1] = l
return ans
在二分查找中设置r为mid而不是mid-1是为了确保不会错过目标值的左边界。如果设置r为mid-1，当mid处于目标值的左边界时，我们将其排除在新的搜索范围之外，从而错过正确的边界。通过设置r为mid，我们保证包含可能的左边界在新的搜索范围内，从而允许算法继续逼近，直到找到确切的左边界。此方法确保每次迭代都缩小搜索范围，同时不会跳过左边界。
在寻找右边界时，当nums[mid] <= target，更新左边界l为mid（而不是mid - 1）是为了确保包含目标值的右边界在搜索范围内。这种处理允许搜索范围逐渐收缩而不排除可能的右边界，从而避免错过任何有效的边界。如果将l设置为mid-1，可能会导致漏掉目标值的实际右边界。这种策略确保算法在逼近目标值的右边界时，始终保持正确的搜索范围。
调整mid的计算方式为mid = l + (r - l + 1) // 2主要是为了确保在二分查找中mid偏向右侧，特别是当l和r非常接近时。这种偏向右侧的策略有助于防止算法陷入无限循环，并确保能够正确找到目标值的右边界。特别是在目标值连续出现且位于数组末尾的情况下，这种调整确保算法能够继续向右逼近，直到找到最后一个目标值的位置。
是的，这种二分查找方法能够准确返回正确的边界值，即使目标值位于数组的开始或结束位置。算法首先确定左边界，确保不会错过开始处的目标值；然后确定右边界，同样确保包括结束处的目标值在内。因此，无论目标值位于数组的哪个位置，该方法都能有效地找到并返回正确的边界值。