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

难度：🟡 Medium | 标签：二分查找 | 状态：⬜ LeetCode 链接

思路

两次二分：

• 左边界：找第一个 >= target 的位置
• 右边界：找第一个 > target 的位置 - 1

代码

class Solution {
    int lower(vector<int>& a, int t) {
        int l = 0, r = a.size();
        while (l < r) { int m = l + (r - l) / 2; if (a[m] >= t) r = m; else l = m + 1; }
        return l;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int lo = lower(nums, target);
        int hi = lower(nums, target + 1) - 1;
        if (lo > hi) return {-1, -1};
        return {lo, hi};
    }
};

复杂度

• 时间 O(log n)，空间 O(1)

易错 / 回顾

• 找右边界用 lower(target + 1) - 1 复用同模板
• 不存在时 lo > hi（包括 lo 越界）
• 也可两套二分（左、右各一套），但复用更优雅