题目
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums 是一个非递减数组
- -109 <= target <= 109
我的代码（Python）
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums:
return [-1, -1]
rs, re = -1, -1
ps, pe = None, None
ns, ne = None, None
if nums[0] == target:
rs = 0
if nums[-1] == target:
re = len(nums) - 1
s, e = 0, len(nums) - 1
if rs == -1 or re == -1:
while s < e:
if s == e - 1:
return [rs if rs != -1 else re, re if re != -1 else rs]
m = (s + e) // 2
if nums[m] == target:
ps = s
pe = m
ns = m
ne = e
break
elif nums[m] < target:
s = m
else:
e = m
# print(f"ps: {ps}, pe: {pe}, ns: {ns}, ne: {ne}")
if rs == -1 and ps is not None and pe is not None:
while ps < pe:
if ps == pe - 1:
rs = pe
break
pm = (ps + pe) // 2
if nums[pm] == target:
pe = pm
else:
ps = pm
if re == -1 and ns is not None and ne is not None:
while ns < ne:
if ns == ne - 1:
re = ns
break
nm = (ns + ne) // 2
if nums[nm] == target:
ns = nm
else:
ne = nm
return [rs, re]点评
思路很容易，而且要求O(logn)本身就是个提示，二分查找。
我的做法是先用一次二分查找，把最左和最右分割在两个区间内，再对两个区间分别二分查找找到最左和最右即可。
时间效率很高，但空间不高，考虑到只有常数额外空间，应该是我的代码里有太多不需要的变量。
我对特殊情况和边界条件处理得太多了。
官方也没什么特别的做法。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog