二分法找目标值左右端点
def search(nums, target):
if not nums:
return [-1, -1]
def search_left(nums, target):
left = 0
right = len(nums)
while left < right:
mid = left + (right-left)/2
if nums[mid] == target:
right = mid
elif nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid
return left if left <= len(nums)-1 and nums[left] == target else -1
def search_right(nums, target):
left = 0
right = len(nums)
while left < right:
mid = left + (right-left)/2
if nums[mid] == target:
left = mid + 1
elif nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid
return right-1 if nums[right-1] == target else -1
return [search_left(nums, target), search_right(nums, target)]
