34. 在排序数组中查找元素的第一个和最后一个位置

别跟我整没用的，暴力大法好

class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# 暴力出奇迹
lis = []
for i in range(len(nums)):
if nums[i] == target:
lis.append(i)
if lis:
return [min(lis),max(lis)]
else:
return [-1,-1]

下面这个思想就是先用二分找到元素位置，后根据这个位置前后摸索
如果也能找到target那么l和r就变动，但因为有了底下两个while 实际上这个算法也并非严格意义上的O（logn）

class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
#设计O（logn）算法
# 先二分定位这个元素的位置 往前往后看看元素一样不一样
# 左闭右开
left,right = 0, len(nums)
while left < right:
middle = (left + right) // 2
if nums[middle] > target:
right = middle # 因为右区间无意义
elif nums[middle] < target:
left = middle + 1
else:
location = middle
break
else:
return [-1,-1]
l,r = location,location
# 往前定位
try: # 防止出现越界以及防止-1索引出现
while nums[l-1] == target and (l-1)>=0:
l -= 1
# 往后定位
while nums[r+1] == target:
r += 1
except:
pass
return [l,r]