查找元素的首末位置 图解题解

这道题真正在问什么

给一个非递减排序、可能含重复元素的数组 nums，找出 target 出现的开始下标和结束下标；不存在就返回 [-1, -1]。题面明确要求 O(log n) 时间——这一条直接排除了从头到尾线性扫描，等于在提示：必须用二分查找，而且是能处理重复元素的二分。

为什么普通二分命中后不能直接返回

普通二分查找在 nums[mid] 等于 target 时立刻返回 mid，但重复元素面前它只能保证「找到了某一个 target」，完全不知道左边、右边还有没有别的 target。拿示例 nums=[5,7,7,8,8,8,10]、target=8 来说，第一次算中点就可能命中中间那个 8，可题目要的是最左的下标 3 和最右的下标 5。

一个看似聪明的补救是：命中后向左右两侧线性扩展，直到值变化为止。但最坏情况下数组全是 target，扩展要走遍整个数组，复杂度退化成 O(n)，违反题目要求。要稳定 O(log n)，扩展这一步也必须是二分的。

命中之后继续收缩，边界是怎么被卡出来的

找左边界时，规则只改一处：nums[mid] 等于 target 时先把 mid 记进候选 res，然后不返回，而是把右端点收到 mid 左边一格，强行到更左的区间里继续找。如果左边还有更早的 target，之后的循环会命中它并覆盖 res；如果没有，后续二分全部落空，res 里留着的就是最左命中。找右边界完全对称：命中后把左端点推到 mid 右边一格，往更右找。

这样做为什么不会漏？靠的是数组的单调性：找左边界时每次砍掉的右半区间里，所有下标都比当前命中的 mid 大，绝不可能藏着「更左」的 target，所以砍掉是安全的。每一轮区间严格缩小一半，可行区间空了循环就停，res 恰好停在边界上。

为什么跑两次二分总时间还是 O(log n)

左边界和右边界是两个方向相反的目标，一次二分没法同时把区间往左右两头收，所以标准写法就是同一套框架跑两次，用一个开关参数决定命中后往哪边继续。每次二分把区间砍半，最多 log n 轮；两次加起来是 2·log n 次比较，常数翻倍但量级仍是 O(log n)。空间上只用左右端点、中点和候选几个变量，O(1)。

容易翻车的三个边界细节

一是循环条件必须允许区间剩单个元素时再查一次，写成左端点不超过右端点；只写严格小于会漏掉最后一个候选。二是中点建议写成 mid = l + (r - l) // 2 而不是左右端点直接相加除二，防止大数组下标相加溢出（Python 无此问题，但换到 Java、C++ 就是真 bug）。三是 target 不存在时两次二分的候选都停在初始值 -1，自然返回 [-1, -1]，不需要任何额外特判——这是「先记候选再收缩」写法附带的好处。

Python

def searchRange(nums, target):
    def bound(findLeft):
        l, r, res = 0, len(nums) - 1, -1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] < target:
                l = mid + 1
            elif nums[mid] > target:
                r = mid - 1
            else:
                res = mid
                if findLeft: r = mid - 1   # 命中继续往左
                else:       l = mid + 1   # 命中继续往右
        return res
    return [bound(True), bound(False)]

C++

class Solution {
    int bound(vector<int>& a, int t, bool left){
        int l = 0, r = a.size() - 1, res = -1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(a[mid] < t) l = mid + 1;
            else if(a[mid] > t) r = mid - 1;
            else { res = mid; if(left) r = mid - 1; else l = mid + 1; }
        }
        return res;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target){
        return {bound(nums, target, true), bound(nums, target, false)};
    }
};

Java

class Solution {
    private int bound(int[] a, int t, boolean left) {
        int l = 0, r = a.length - 1, res = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (a[mid] < t) {
                l = mid + 1;            // mid 太小，找右半
            } else if (a[mid] > t) {
                r = mid - 1;            // mid 太大，找左半
            } else {
                res = mid;              // 命中，先记下
                if (left) r = mid - 1;  // 卡左边界：继续往左
                else      l = mid + 1;  // 卡右边界：继续往右
            }
        }
        return res;
    }
    public int[] searchRange(int[] nums, int target) {
        return new int[]{bound(nums, target, true), bound(nums, target, false)};
    }
}