二分查找找到目标值的第一个位置和最后一个位置
def lower_bound(nums: List, target: int) -> int:left, right = 0, len(nums) - 1# 闭区间
while left <= right:# 区间不为空
# 循环不变量：
# nums < target
# nums >= target
mid = (left + right) // 2
if nums < target:
left = mid + 1# 范围缩小到
else:
right = mid - 1# 范围缩小到
return left
class Solution:
def searchRange(self, nums: List, target: int) -> List:
start = lower_bound(nums, target)# 选择其中一种写法即可
if start == len(nums) or nums != target:
return [-1, -1]# nums 中没有 target
# 如果 start 存在，那么 end 必定存在
end = lower_bound(nums, target + 1) - 1
return
其中，start == len(nums)是什么情况？
end = lower_bound(nums, target + 1) - 1又是什么情况 在这个算法中，我们需要找到一个有序数组中目标值 `target` 的第一个和最后一个位置。`lower_bound` 函数用于定位第一个大于或等于目标值的位置。
1. **`start == len(nums)` 的情况**：
- 当 `lower_bound(nums, target)` 返回的 `start` 值等于数组长度时，意味着在整个数组中没有找到大于或等于 `target` 的元素。这也就是说，`target` 不在数组中。
- 这通常会发生在 `target` 大于数组中所有元素的情况下。
2. **`end = lower_bound(nums, target + 1) - 1` 的情况**：
- 首先，`lower_bound(nums, target + 1)` 寻找的是第一个大于 `target` 的位置。通过减去 1，我们得到了 `target` 出现的最后一个位置，因为它是最后一个等于 `target` 的位置。
- 这是一种技巧性的用法：通过找一个比目标值大1的值的起始位置来推断目标值的最后位置。
总结：
- `start == len(nums)` 用来判断目标值在数组内是否存在。
- `end = lower_bound(nums, target + 1) - 1` 用来精确定位目标值最后出现的位置。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]