二分查找找到目标值的第一个位置和最后一个位置

Terence888

def lower_bound(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1  # 闭区间 [left, right]
    while left <= right:  # 区间不为空
        # 循环不变量：
        # nums[left-1] < target
        # nums[right+1] >= target
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # 范围缩小到 [mid+1, right]
        else:
            right = mid - 1  # 范围缩小到 [left, mid-1]
    return left

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = lower_bound(nums, target)  # 选择其中一种写法即可
        if start == len(nums) or nums[start] != target:
            return [-1, -1]  # nums 中没有 target
        # 如果 start 存在，那么 end 必定存在
        end = lower_bound(nums, target + 1) - 1
        return [start, end]

其中，

start == len(nums)

是什么情况？

end = lower_bound(nums, target + 1) - 1

又是什么情况

FishC

在这个算法中，我们需要找到一个有序数组中目标值 `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 小助理，如未能正确解答您的问题，请继续追问。