34. 查找元素首尾位置
题目描述
输入一个按非递减顺序排好的整数数组 nums 和整数 target。
返回一个长度为 2 的数组：target 在 nums 中第一次出现的下标和最后一次出现的下标，下标从 0 开始。target 不在数组中时返回 [-1,-1]。
要求时间复杂度为 O(log n)。
示例 1
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
解释：两个 8 分别在下标 3 和 4。
示例 2
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]
解释：数组中没有 6。
示例 3
输入：nums = [], target = 0 输出：[-1,-1]
解释：空数组中找不到任何值。
数据范围
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9nums是非递减的。-10^9 <= target <= 10^9
解题思路
分别寻找左右 lower_bound。
为什么正确
左界左侧小于 target，右界右侧大于 target。
复杂度分析
时间 O(log n)，额外空间 O(1)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def searchRange(self,a,t):
def lo(x):
l,h=0,len(a)
while l<h:
m=(l+h)//2
if a[m]<x:l=m+1
else:h=m
return l
l=lo(t);r=lo(t+1)-1
return [l,r] if l<len(a) and a[l]==t else [-1,-1]class Solution {
public int[] searchRange(int[] a, int t) {
int l = lo(a, t), r = lo(a, t + 1) - 1;
return l < a.length && a[l] == t ? new int[]{l, r} : new int[]{-1, -1};
}
private int lo(int[] a, int x) {
int l = 0, h = a.length;
while (l < h) {
int m = (l + h) / 2;
if (a[m] < x) l = m + 1;
else h = m;
}
return l;
}
}class Solution {
public:
vector<int> searchRange(vector<int>& a, int t) {
auto lo = [&](int x) {
int l = 0, h = a.size();
while (l < h) {
int m = (l + h) / 2;
if (a[m] < x) l = m + 1;
else h = m;
}
return l;
};
int l = lo(t), r = lo(t + 1) - 1;
return l < (int)a.size() && a[l] == t ? vector<int>{l, r} : vector<int>{-1, -1};
}
};func searchRange(a []int, t int) []int {
lo := func(x int) int {
l, h := 0, len(a)
for l < h {
m := (l + h) / 2
if a[m] < x {
l = m + 1
} else {
h = m
}
}
return l
}
l, r := lo(t), lo(t+1)-1
if l < len(a) && a[l] == t {
return []int{l, r}
}
return []int{-1, -1}
}var searchRange = function(a, t) {
const lo = (x) => {
let l = 0, h = a.length;
while (l < h) {
const m = (l + h) >> 1;
if (a[m] < x) l = m + 1;
else h = m;
}
return l;
};
const l = lo(t), r = lo(t + 1) - 1;
return l < a.length && a[l] === t ? [l, r] : [-1, -1];
};function searchRange(a: number[], t: number): number[] {
const lo = (x: number): number => {
let l = 0, h = a.length;
while (l < h) {
const m = (l + h) >> 1;
if (a[m] < x) l = m + 1;
else h = m;
}
return l;
};
const l = lo(t), r = lo(t + 1) - 1;
return l < a.length && a[l] === t ? [l, r] : [-1, -1];
};