在排序数组中查找元素的第一个和最后一个位置

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 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]

💭 模拟答题者思考

1. 我先想暴力：从左到右扫描，遇到 target 记录首次和末次下标，O(n)——能过但题目要求 O(log n)。

2. 重复在哪里？数组非递减，target 若存在必是一段连续相等区间；普通二分只找「任意一个」命中点，无法直接得到首尾。

3. 关键转化：把问题拆成两次二分——第一次找左边界（第一个等于 target 的位置）：命中时仍向左缩 r = mid - 1 并暂存 mid；第二次找右边界：命中时向右缩 l = mid + 1 并暂存 mid。

4. 例 [5,7,7,8,8,10], target=8：找左边界时 mid=2→7 缩右，mid=4→8 记录 4 再缩左得 3；找右边界时从 3 出发最终记录 4。

5. 两次二分各 O(log n)，总 O(log n)；若左边界为 -1 说明不存在，直接返回 [-1,-1]。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`l, r`	int	定义：当前待搜索区间的左右边界下标维护：若 `target` 存在，其「左边界」或「右边界」始终在 `[l, r]` 内更新：每轮二分根据 `nums[mid]` 与 `target` 的关系，将区间收缩一半；命中时按找左/右边界方向继续缩
`mid`	int	定义：当前区间中点下标 `(l + r) // 2` 维护：将区间切成左段 `[l, mid]` 与右段 `[mid+1, r]` 更新：每轮二分重新计算；若 `nums[mid] == target` 则记录为候选边界并继续向目标方向搜索
`bound`	int	定义：当前已找到的候选边界下标，初始为 `-1` 维护：找左边界时记录最小的等于 `target` 的下标；找右边界时记录最大的等于 `target` 的下标更新：每当 `nums[mid] == target` 时更新 `bound = mid`，并分别令 `r = mid - 1`（向左找）或 `l = mid + 1`（向右找）

⌨️ 落码步骤

1. 定义辅助函数 find_bound(is_first)：l=0, r=len(nums)-1, bound=-1

2. 当 l <= r：取 mid；若 nums[mid] == target，令 bound = mid，is_first 则 r = mid - 1 否则 l = mid + 1

3. 若 nums[mid] < target 则 l = mid + 1，否则 r = mid - 1

4. 返回 bound；主函数先求左边界 first，若为 -1 返回 [-1,-1]

5. 再求右边界 last，返回 [first, last]

💻 代码实现

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        def find_bound(is_first: bool) -> int:
            l, r = 0, len(nums) - 1
            bound = -1
            while l <= r:
                mid = (l + r) // 2
                if nums[mid] == target:
                    bound = mid
                    if is_first:
                        r = mid - 1      # 继续向左找更小的左边界
                    else:
                        l = mid + 1      # 继续向右找更大的右边界
                elif nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return bound

        first = find_bound(True)
        if first == -1:
            return [-1, -1]
        last = find_bound(False)
        return [first, last]

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto findBound = [&](bool isFirst) {
            int l = 0, r = (int)nums.size() - 1, bound = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (nums[mid] == target) {
                    bound = mid;
                    if (isFirst)
                        r = mid - 1;     // 向左找左边界
                    else
                        l = mid + 1;     // 向右找右边界
                } else if (nums[mid] < target)
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            return bound;
        };

        int first = findBound(true);
        if (first == -1) return {-1, -1};
        int last = findBound(false);
        return {first, last};
    }
};
// 时间 O(log n)，空间 O(1)

📈 复杂度分析

时间复杂度 O(log n)

空间复杂度 O(1)

⚠️ 常见坑

❗ 找左边界时命中后必须 r = mid - 1（不是 l = mid + 1），找右边界时命中后必须 l = mid + 1——方向搞反会得到错误边界。

❗ 命中时不能直接 return mid：数组中可能有多个 target，需要继续向目标方向搜索才能拿到真正的首尾。

❗ 空数组 nums = [] 时 r = -1，循环不进入、bound 保持 -1，应直接返回 [-1,-1] 而非越界访问。

🔍 必测边界 Case

Case 1：空数组

nums = [], target = 0 → [-1,-1]

Case 2：目标不存在

nums = [5,7,7,8,8,10], target = 6 → [-1,-1]

Case 3：全数组均为 target

nums = [2,2,2,2], target = 2 → [0,3]

Case 4：仅一个 target

nums = [1,2,3], target = 2 → [1,1]（左边界与右边界相同）