题目描述
升序数组中找 target 的起始和结束下标，不存在返回 [−1, −1]。
nums = [5, 7, 7, 8, 8, 10]
target = 8
输出 = [3, 4]
思路解析
如果数组全是 8，向两边线性扩会退化成 O(n)。更稳的办法：分别二分找「第一个 ≥8」和「第一个 >8」这两条边界。
复用下界二分：找「第一个 ≥ 8」得到左边界 3；再找「第一个 > 8」得到 5，它前一位 4 就是右边界。两次 O(log n)。
找左界 · l=0,r=6：找「第一个 ≥ 8」。mid=3 处是 8，满足，收右 r=3，继续往左看有没有更早的 8。
找左界 · 收缩：mid=1 是 7 < 8，左界在右边，l=2。再二分 [2,3) → mid=2 是 7<8 → l=3，收敛。
左界 = 3：收敛到 3，这是第一个 8 的位置，左边界 = 3。
找右界 · 第一个 >8：再找「第一个 > 8」。mid=4 是 8，不满足 >8，l 右移到 5。
右界二分收敛：mid=5 是 10 > 8，满足，收 r=5。区间收敛到 5——这是「第一个 >8」的位置。
右界 = 5 − 1 = 4：「第一个 >8」是 5，它前一位 4 就是最后一个 8。最终答案 [3, 4]。
「某值的左右边界 / 出现次数」都能化成两次下界二分：第一个 ≥t 和 第一个 >t，相减还能得出现次数。
参考代码（Python）
Python
1def lower(t): # 第一个 >= t 的位置
2 l, r = 0, len(nums)
3 while l < r:
4 m = (l + r) // 2
5 if nums[m] >= t: r = m
6 else: l = m + 1
7 return l
8lo = lower(target)
9if lo == len(nums) or nums[lo] != target: return [-1, -1]
10return [lo, lower(target + 1) - 1] # 右界= 第一个>t 再减1复杂度分析
- 时间复杂度：O(log n) —— 两次二分
- 空间复杂度：O(1) —— 几个指针
套路模板
记住骨架：写一个 lower(t)，左界=lower(t)、右界=lower(t+1)−1、出现次数=lower(t+1)−lower(t)。一个函数解决一类边界题。
Python
1# 第一个 >= t 的位置(下界二分)
2def lower(t):
3 l, r = 0, n
4 while l < r:
5 m = (l + r) // 2
6 if nums[m] >= t: r = m
7 else: l = m + 1
8 return l
9left, right = lower(t), lower(t + 1) - 1 # [左界, 右界]易错点
- ❌ 不判 target 是否存在 → ✅ 先看 lower(t) 处是不是 target（lower 只给"应插入位置"，未必真有该值）
- ❌ 右界单独写一套二分 → ✅ 复用 lower(t+1) − 1（少写一遍逻辑、不易错）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。