在排序数组中查找元素的第一个和最后一个位置
Find First and Last Position of Element in Sorted Array
本机进度仅保存在当前浏览器
题目描述
给你一个按非递减顺序排列的整数数组 nums 和一个目标值 target，请找出目标值在数组中的开始位置和结束位置；不存在则返回 [-1, -1]。要求时间复杂度 O(log n)。
示例：nums = [5, 7, 7, 8, 8, 10]，target = 8，输出 [3, 4]。
解题思路
- 普通二分命中即返回，无法确定边界；改写为「找左边界」与「找右边界」两次独立二分。
- 找左边界：nums[mid] >= target 时 r = mid - 1 并记录 mid，否则 l = mid + 1，最终得到第一个 >= target 的位置。
- 找右边界同理，条件 nums[mid] <= target 时继续向右收缩。
- 也可以用统一写法 lowerBound(target) 与 lowerBound(target + 1) - 1，思路是把边界查找归约为"第一个大于等于 x 的位置"。
参考实现
查看参考实现Python · 建议先自行作答
def searchRange(nums, target):
def lowerBound(x):
# 第一个 >= x 的下标
l, r, ans = 0, len(nums) - 1, len(nums)
while l <= r:
mid = l + (r - l) // 2
if nums[mid] >= x:
ans, r = mid, mid - 1
else:
l = mid + 1
return ans
lo = lowerBound(target)
hi = lowerBound(target + 1) - 1
if lo <= hi:
return [lo, hi]
return [-1, -1]