emmm依然按照递归的思路做了一下题，但是为什么时间上只超过了不到百分之10的人啊，难度递归真的太慢了嘛还是因为我重复查找了每一个target啊，感觉应该是因为后者吧。这个算法的时间复杂度是O（logN），空间复杂度是O（1）。嗯再看看别人怎么实现的吧。啊我知道了，因为我没有利用好数组有序的这个特性导致在递归的时候同时递归了两边的区间，而实际上只需要递归左区间或者右区间就可以了，啊我尝试更改实现1感觉如果按照2的思路的话得拆分成两个方法（除非使用targt+1的技巧，但是那样写出来应该就是和实现2把left_func拆分成一个独立的方法而已）。所以按这样看到话，我的思路慢的原因就这样花费了多余的时间去找到了每个和target值相对应的值才求出了左右边界。
class Solution:
def searchRange1(self, nums: List[int], target: int) -> List[int]:
self.left_idx, self.right_idx = -1, -1
if nums:
self.recursion(nums, target, 0, len(nums)-1)
return [self.left_idx, self.right_idx]
def recursion(self, nums, target, left, right):
mid = (left + right) // 2
if nums[mid] == target:
if mid == 0 or nums[mid-1] < target:
self.left_idx = mid
if mid == len(nums)-1 or nums[mid+1] > target:
self.right_idx = mid
if left >= right:
return
self.recursion(nums, target, left, mid)
self.recursion(nums, target, mid+1, right)
def searchRange2(self,nums, target):
print("------------")
def left_func(nums,target):
left, right = 0, len(nums)-1
while(left<=right): # using <= is due to we want to include the target into a intervel with length == 1
mid = (left+right)//2
print("left{}, mid{}, right{}".format(left, mid, right))
print("nums mid{}, target{}".format(nums[mid], target))
if nums[mid] >= target:
right = mid-1
if nums[mid] < target:
left = mid+1
return left
a = left_func(nums,target)
b = left_func(nums,target+1)
"""
for a == len(nums), it happens when target is bigger than the biggest number in the list
for nums[a] != target, it happens when target is small than the smallest number in the list
"""
if a == len(nums) or nums[a] != target:
return [-1,-1]
else:
return [a,b-1]PREVIOUSlc033.搜索旋转排序数组
NEXTmq012.盛最多水的容器