class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums:
return [-1, -1]
l = self.low_bound(nums, target)
r = self.high_bound(nums, target)
if l >= len(nums) or nums[l] != target: # 也可以通过 l > r
return [-1, -1]
return [l, r-1]
def low_bound(self, nums, target):
l = 0
r = len(nums) - 1 # 左闭右闭
while l <= r:
mid = l + (r - l) // 2
if nums[mid] < target: # 求上下边界时, 等于没有返回。也导致后续输出后判断是否根本没找到
l = mid + 1
elif nums[mid] >= target:
r = mid - 1
return l # 注意l
def high_bound(self, nums, target):
l = 0
r = len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] <= target:
l = mid + 1
elif nums[mid] > target:
r = mid - 1
return l # 注意l, 最后输出upper bound - 1
时间复杂度：O(log(n))
空间复杂度：O(1)
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums:
return [-1, -1]
l = self.get_lower(nums, target)
r = self.get_higher(nums, target)
if l < len(nums) and l < r:
return [l, r-1]
return [-1, -1]
def get_lower(self, nums, target):
l = 0
r = len(nums)
while l < r:
mid = l + (r - l) // 2
if nums[mid] < target:
l = mid + 1
else:
r = mid
return l
def get_higher(self, nums, target):
l = 0
r = len(nums)
while l < r:
mid = l + (r - l) // 2
if nums[mid] <= target:
l = mid + 1
else:
r = mid
return l