在排序数组中查找元素的第一个和最后一个位置
Find First and Last Position of Element in Sorted Array
在非递减数组里找出 target 第一次和最后一次出现的下标，找不到返回 [-1, -1]。
在力扣中练习题目描述
给你一个按照非递减顺序排列的整数数组 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] <= 109nums是一个非递减数组-109 <= target <= 109
解题思路
两次二分 · 分别找左右边界
命中之后不停手，继续往左／往右压缩区间
普通二分命中 target 就结束，得到的只是某一次出现的位置。要找一整段重复值的端点，需要把“命中后往哪边继续找”也纳入规则。
自拟主例 nums = [1,2,2,4,4,4,4,7,9]，target = 4，返回 [3,6]。第一次命中位于重复段内部，不能直接当作任一端点。
同一个有序数组执行两次二分，命中后还要继续向目标方向收缩。
找最左时，命中先暂存 mid，再把右端改为 mid-1；找最右时同样暂存，但把左端改为 mid+1。值太小、太大时分别丢弃不可能包含答案的半边。
两次查找都使用闭区间 [left,right]，所以循环条件是 left <= right。退出后暂存值才是最终端点。若第一次始终没有命中，直接返回 [-1,-1]。
易错点
- 命中后直接 return，只拿到某个 target 的下标，不是边界。
- 找右边界时把 left = mid + 1 和 right = mid - 1 写反，区间朝反方向收缩。
- 闭区间模板却把循环写成 left < right：只剩一个候选点时直接退出，会漏掉答案。
STL · lower_bound + upper_bound
用现成的「第一个 ≥ x」和「第一个 > x」拼出区间
同样是 O(log n) 的库函数写法；重点是区分第一个不小于与第一个大于 target 的位置。
C++ 的 lower_bound / upper_bound 做的正是上面两次二分：
lower_bound(begin, end, target)：第一个 ≥ target 的位置；upper_bound(begin, end, target)：第一个 > target 的位置。
于是答案区间就是 [lower_bound, upper_bound)。两者相等说明一个 target 都没有，返回 {-1, -1}；否则左端点是 first - begin，右端点是 last - begin - 1。
注意 upper_bound 返回的是第一个大于 target 的位置，所以右边界要减一。这个「左闭右开」的表示是 STL 的通用约定，想清楚之后比手写边界更不容易错。
面试时如果允许用 STL，这是最稳的写法；如果要求手写，记住上面那两句「第一个 ≥ x」「第一个 > x」，模板可以现推。
- 1lower_bound 找到第一个 ≥ target 的位置。
- 2upper_bound 找到第一个 > target 的位置。
- 3两者相等说明不存在，返回 {-1, -1}。
- 4左端点取 first，右端点取 last - 1。
易错点
- upper_bound 的结果忘记减一，右端点会落在 target 后面一格。
- 用 first == nums.end() 判不存在：target 比所有元素都大时 first 才是 end，判不完整。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [1,2,2,4,4,4,4,7,9], target = 4同一个有序数组执行两次二分，命中后还要继续向目标方向收缩。
查看 C++ 代码
延伸阅读
- 「第一个 ≥ x」和「第一个 > x」是二分的两个原子操作，几乎所有边界问题都能由它们组合出来。
- 手写二分时坚持只用一种区间表示（左闭右开 [left, right) 或闭区间 [left, right]），边界错误大多来自混用。
- 如果数组是降序，把比较符号整体反过来即可，思路完全不变。