Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O (log n ).
If the target is not found in the array, return [-1, -1] .
自己写的答案：
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# 判断列表长度
if len(nums) == 0:
return [-1, -1]
elif len(nums) == 1:
return [0, 0] if nums[0] == target else [-1, -1]
else:
low = self.search_first(nums, target)
high = self.search_last(nums, target)
return [low, high]
def search_first(self, nums: List[int], target: int):
low = 0
high = len(nums) - 1
while low <= high:
mid = low + (high - low >> 1)
if nums[mid] >= target:
high = mid - 1
else:
low = mid + 1
if low <len(nums) and nums[low] == target:
return low
else:
return -1
def search_last(self, nums: List[int], target: int):
low = 0
high = len(nums) - 1
while low <= high:
mid = low + (high - low >> 1)
if nums[mid] > target:
high = mid - 1
else:
low = mid + 1
if high <len(nums) and nums[high] == target:
return high
else:
return -1
其实查找最后一个和查找第一个是可以合并成一个函数的，然后通过一个标志位来判断是找第一个还是最后一个，然后确定来更新low还是更新high，这里我就不写了