长沙网站制作作途牛旅游网

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

思路

二分查找，
口诀：左右右，求左段区间的右端点，动r

解题方法

两次二分查找

复杂度

时间复杂度: $O(logn)$ 二次两份查找

空间复杂度: $O(1)$ 若干中间变量

Code

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:if not nums: return [-1, -1]n = len(nums)l, r = 0, n - 1res = [-1, -1]# 确定左区间while l < r:mid = l + r >> 1if nums[mid] >= target:r = midelse:l = mid + 1if nums[l] == target:res[0] = l# 确定右区间r = n - 1while l < r:mid = l + r + 1>> 1if nums[mid] <= target:l = midelse:r = mid - 1if nums[l] == target: res[1] = rreturn res