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

问题拆解

非递减数组里找 target 出现的起止下标，不存在返回 [-1, -1]，要求 O(log n)。

普通二分找到一个 target 就停，但它停在哪个 target 上是不确定的；从命中点向两边线性扩展的话，遇到全数组都是 target 的极端情况会退化成 O(n)。所以需要的不是“找到任意一个”，而是“边界二分”：即使中点命中了 target 也不停下，继续向左压缩，逼出第一次出现的位置。

这里有个省一半代码的观察：右边界不用单独写一套“找最后一个”的二分。定义 lowerBound(x) 为“第一个大于等于 x 的下标”，那么 target 的左边界就是 lowerBound(target)，而 target 的最后一次出现，恰好在 lowerBound(target + 1) 的前一个位置。一个函数调两次，逻辑完全对称。

普通二分回答“在不在”，边界二分回答“从哪开始”；后者的要诀是命中时不返回，把命中当成“答案可能还在左边”继续收缩。

两次 lower_bound

lowerBound 用左闭右开区间 [left, right)：nums[mid] >= x 时答案在 mid 或更左，收缩 right = mid（注意不是 mid - 1，因为 mid 本身仍是候选）；否则 left = mid + 1。循环结束时 left == right，就是第一个 >= x 的位置，全部元素都小于 x 时它等于数组长度。

public int[] searchRange(int[] nums, int target) {
    int start = lowerBound(nums, target);
    if (start == nums.length || nums[start] != target) {
        return new int[]{-1, -1}; // 不存在
    }
    int end = lowerBound(nums, target + 1) - 1;
    return new int[]{start, end};
}

// 第一个 >= x 的下标，不存在则返回 nums.length
private int lowerBound(int[] nums, int x) {
    int left = 0, right = nums.length; // 左闭右开
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= x) {
            right = mid; // mid 仍是候选，不能跳过
        } else {
            left = mid + 1;
        }
    }
    return left;
}

def searchRange(nums: List[int], target: int) -> List[int]:
    def lower_bound(x: int) -> int:
        # 第一个 >= x 的下标，不存在则返回 len(nums)
        left, right = 0, len(nums)  # 左闭右开
        while left < right:
            mid = (left + right) // 2
            if nums[mid] >= x:
                right = mid  # mid 仍是候选，不能跳过
            else:
                left = mid + 1
        return left

    start = lower_bound(target)
    if start == len(nums) or nums[start] != target:
        return [-1, -1]  # 不存在
    return [start, lower_bound(target + 1) - 1]

func searchRange(nums []int, target int) []int {
    // 第一个 >= x 的下标，不存在则返回 len(nums)
    lowerBound := func(x int) int {
        left, right := 0, len(nums) // 左闭右开
        for left < right {
            mid := (left + right) / 2
            if nums[mid] >= x {
                right = mid // mid 仍是候选，不能跳过
            } else {
                left = mid + 1
            }
        }
        return left
    }
    start := lowerBound(target)
    if start == len(nums) || nums[start] != target {
        return []int{-1, -1} // 不存在
    }
    return []int{start, lowerBound(target+1) - 1}
}

pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
    // 第一个 >= x 的下标，不存在则返回 nums.len()
    fn lower_bound(nums: &[i32], x: i32) -> usize {
        let (mut left, mut right) = (0, nums.len()); // 左闭右开
        while left < right {
            let mid = left + (right - left) / 2;
            if nums[mid] >= x {
                right = mid; // mid 仍是候选，不能跳过
            } else {
                left = mid + 1;
            }
        }
        left
    }
    let start = lower_bound(&nums, target);
    if start == nums.len() || nums[start] != target {
        return vec![-1, -1]; // 不存在
    }
    let end = lower_bound(&nums, target + 1) - 1;
    vec![start as i32, end as i32]
}

拿到 start 后必须做两个检查再宣布找到：start == n 说明所有元素都比 target 小，nums[start] != target 说明 target 落在两个元素的缝隙里——两种情况都要返回 [-1, -1]。检查通过后 lowerBound(target + 1) - 1 一定不会越界也一定等于 target，因为至少 start 这个位置托着底。

和普通二分的差异集中在一行上：普通二分 nums[mid] == target 时直接 return mid；边界二分把等于并入“收缩右边界”的分支，宁可多走 log n 步也要把答案压到最左。相应地循环条件用 left < right、右指针取 mid 而非 mid - 1，三处必须配套，混搭就会死循环或漏解。

复杂度

指标	复杂度	原因
时间	`O(log n)`	两次二分，各折半 log n 次
空间	`O(1)`	只用常数个指针

可以迁移的模式

lowerBound(x) 是二分的原子操作：找右边界不用另写一套，用 lowerBound(x + 1) - 1 换算即可；
边界二分的不变式——“答案始终在 [left, right) 内”——决定了每个分支怎么收缩，想清楚不变式就不会写错加一减一；
二分返回的下标使用前先验证（越界、值是否相等），“第一个 >= x”不等于“x 存在”。

把比较条件从 >= x 换成任意单调谓词，这套模板就能二分“第一个满足条件的位置”，适用面远不止有序数组查值。