面试150 在排序数组中查找元素的第一个和最后一个元素

思路1

直接搜寻法，通过记录target所对应的索引值，最后返回第一个和最后一个下标即可。

class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: if target not in nums: return [-1,-1] res=[] for i in range(len(nums)): if nums[i]==target: res.append(i) return [res[0],res[-1]]

思路2

通过两次二分查找定位目标值 target 的起始和结束位置。首先，如果 target 不在数组中，直接返回 [-1, -1]。否则，定义一个 binary 函数，用于查找第一个大于等于目标值的位置。第一次调用 binary(0, n-1, target) 找到 target 出现的最左位置 Left，第二次调用 binary(0, n-1, target+1) - 1 找到 target 出现的最右位置 Right。由于第二次查找的是 target+1，减一后刚好落在最后一个 target 上。最后检查边界条件并返回 [Left, Right]。

class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: if target not in nums: return [-1,-1] def binary(left,right,target): while left<=right: middle=(left+right)//2 if nums[middle]<target:  left=middle+1 elif nums[middle]>=target:  right=middle-1 return left n=len(nums) Left=binary(0,n-1,target) Right=binary(0,n-1,target+1)-1 if Left==n and nums[Left]!=nums[Right]: return [-1,-1] return [Left,Right]