| 题目链接 | 34. 在排序数组中查找元素的第一个和最后一个位置 |
|---|---|
| 思路 | 二分法 |
| 题解链接 | 【视频讲解】二分查找总是写不对？三种写法，一个视频讲透！（Python/Java/C++/C/Go/JS） |
| 关键点 | 模板题；应当熟练掌握 |
| 时间复杂度 | \(O(\log n)\) |
| 空间复杂度 | \(O(1)\) |
代码实现：
# 闭区间
def lower_bound(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
# 循环不变量：
# nums[left-1] < target
# nums[right+1] >= target
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
# 左闭右开区间
def lower_bound2(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
# 循环不变量：
# nums[left] < target
# nums[right] >= target
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
# 开区间
def lower_bound3(nums, target):
left, right = -1, len(nums)
while left + 1 < right:
mid = (left + right) // 2
# 循环不变量：
# nums[left] < target
# nums[right] >= target
if nums[mid] < target:
left = mid
else:
right = mid
return right
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]
end = lower_bound3(nums, target+1) - 1
return [start, end]