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

Terence888

1. def lower_bound(nums: List[int], target: int) -> int:
   
2.     left, right = 0, len(nums) - 1  # 闭区间 [left, right]
   
3.     while left <= right:  # 区间不为空
   
4.         # 循环不变量：
   
5.         # nums[left-1] < target
   
6.         # nums[right+1] >= target
   
7.         mid = (left + right) // 2
   
8.         if nums[mid] < target:
   
9.             left = mid + 1  # 范围缩小到 [mid+1, right]
   
10.         else:
    
11.             right = mid - 1  # 范围缩小到 [left, mid-1]
    
12.     return left
    
13. 
    

复制代码

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

复制代码

其中，

1. start == len(nums)

复制代码

是什么情况？

1. 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 小助理，如未能正确解答您的问题，请继续追问。