LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置：左边界与右边界的对称

题目：两个边界

LeetCode 34：升序数组中找 target 的起始与结束位置——O(log n)——找不到返回 [-1, -1]。

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

「两个边界」的对应关系：左边界 = 第一个 ≥ target 的位置；右边界 = 最后一个 ≤ target 的位置 = 「第一个 > target 的位置 - 1」——「两个模板」覆盖一切：「lower_bound」（第一个 ≥ x）与「upper_bound」（第一个 > x）——「C++ STL 的命名」——「两个函数」是二分边界的原子操作**。

统一心智：左闭右开 + 找第一个 ≥ x

「lower_bound」的模板：「左闭右开 [left, right)」+「找第一个 ≥ x」——「循环不变量」：left 之前全 < x、right 之后全 ≥ x——「不变量」的两端——循环收缩到 left == right——「left 就是第一个 ≥ x」（或 n）：

def lower_bound(nums, x):
    left, right = 0, len(nums)        # [left, right)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < x:
            left = mid + 1            # [mid+1, right) —— mid < x
        else:
            right = mid               # [left, mid) —— mid ≥ x
    return left                       # 第一个 ≥ x

「upper_bound」的推导：「第一个 > x」=「第一个 ≥ x+1」——「调用 lower_bound(x+1)」——「 upper_bound(x) = lower_bound(x+1)」——「一个函数」覆盖两个——「但整数之外呢」（浮点数的 x+1 不成立——「独立的 upper_bound」：条件从 nums[mid] < x 改为 nums[mid] <= x——「一行之差」的姊妹函数——**「两个模板」的对称性。

「本题的组装」：「左边界 = lower_bound(target)」；右边界 = lower_bound(target+1) - 1——「组合两个原子」——「存在的验证」：左边界 == n 或 nums[left] != target——「验证后返回」——「验证的两种」：lower_bound 找到的可能是不存在（左边界越界或值不等——「越界检查」——「组合与验证」的完整代码：

def search_range(nums, target):
    def lower_bound(x):
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < x:
                left = mid + 1
            else:
                right = mid
        return left

    left = lower_bound(target)
    if left == len(nums) or nums[left] != target:
        return [-1, -1]
    right = lower_bound(target + 1) - 1
    return [left, right]

graph TD
    A[lower_bound(x): 第一个 ≥ x<br/>左闭右开模板] --> B[左边界 = lower_bound(target)]
    A --> C[右边界 = lower_bound(target+1) - 1]
    B & C --> D[验证: left 越界或值不等 → [-1,-1]]

「边界二分」的变体家族

「变体的翻译」：「第一个大于 x」（upper_bound）、「最后一个小于 x」（lower_bound(x) - 1）、「最后一个 ≤ x」（upper_bound(x) - 1）——「全部由两个原子函数推导」——「变体的记忆负担」消失——「两个原子函数的签名」：lower_bound(x) = 第一个 ≥ x——upper_bound(x) = 第一个 > x——「记忆的两个原子」而非「四个变体」——「推导式记忆」优于「列表记忆」。「二分答案」的衔接（爬楼梯篇的答案二分——「答案二分的实现」就是 lower_bound 的变体——「验证函数」的单调判断——「二分答案的边界」——「答案空间的 lower_bound」——「34 题是答案二分的预科」。

「工程中的边界二分」：「时间窗口的查询」（日志系统的时间范围检索（「时间戳的边界」——lower_bound 找起始时间戳、upper_bound 找结束——「时间序列的检索」——TSDB 的查询（库内时序数据库篇——「按时间范围查样本」——「数据库索引的 B+ 树范围查询」（「索引的下界与上界」——「SQL 的 BETWEEN」底层——「边界二分」是数据库范围查询的内核——「这道题」是理解索引范围查询的理论基础——「从算法题到数据库内核」的贯通。

二分边界的进阶：lower_bound/upper_bound 的完整推导与工程映射

二分边界的进阶：lower_bound/upper_bound 的完整推导体系与工程映射。「lower_bound 的完整推导」：「语义的精确定义」——lower_bound(x) 返回「第一个 ≥ x 的元素位置」——「为什么是 ≥」——「等号在 lower」——「lower_bound 的不变量」——「不变量」：left 之前全部 < x，right 之后全部 ≥ x——「不变量的维持」——每一步移动保持不变量——「不变量的验证」——循环结束时 left == right——「不变量 → left 就是第一个 ≥ x」——「推导完成」——「upper_bound 的推导」——upper_bound(x) 返回「第一个 > x 的位置」——「语义的切换」——「条件从 ≥ 改为 >」——「代码的对应」（if nums[mid] <= x: left = mid+1——「等号移到左分支」——「一行之差」——「两个函数的对称性」。「变体的推导矩阵」：「四个变体的统一推导」——「第一个 ≥ x」（lower）、「第一个 > x」（upper）、「最后一个 ≤ x」（upper(x)-1）、「最后一个 < x」（lower(x)-1）——「四变体 ← 两原子」——「推导式记忆」——「推导的练习」（给定一个变体，用两个原子写出——「推导的能力」——「从推导到直觉」——「直觉」的形成——「反复推导」后的条件反射——「条件反射」的用法（面试时不用推导直接写——「推导是练习方法，直觉是面试输出」。「工程映射」：「数据库的范围查询」——「B+ 树的范围检索」——lower_bound/upper_bound 在 B+ 树的实现——「索引的下界与上界」——「SQL 的 BETWEEN」的底层——「范围查询」的代价（「log n + 结果数」——「范围查询的代价」——「时间序列的边界检索」（时序数据库篇——「时间戳的 lower/upper」——「日志的时间范围检索」——「日志系统」的索引——「二分」在存储内核的角色——「704 到内核」的贯通——「工程映射」：「搜索插入位置（35）」——「lower_bound」的直接应用——「搜索旋转矩阵 II」（「二维的二分」——「行二分+列二分」——「二分的二维化」——「二分」的多维扩展——「从一维到多维」——「二分的泛化」——「矩阵的二分」——「二分的家族」：704（精确）、34（边界）、35（插入）、33/81（旋转）、153（最小）、4（中位数）、「答案二分」（875/410）——「家族的树形」——「根是 704」——「34 是第一个分支」——「答案二分是终极形态」——「二分的家族树」——「每个家族成员」共享「单调判定+范围收缩」的 DNA——「DNA」的一致性。二分边界的进阶总结：lower/upper 的完整推导（不变量的建立与维持）+变体推导矩阵（四变体←两原子）+工程映射（B+ 树范围查询、时序检索、SQL BETWEEN）+家族树（704→34→答案二分的进化链）——「二分边界」的掌握标准：「给定任何边界变体，能从两个原子推导出来」——「推导能力」优于「背诵能力」——「推导」的训练方式：「每写一个边界二分，先写下不变量，再推代码」——「不变量先行」的习惯——「不变量」让二分的正确性从「祈祷」变成「证明」**。

二分答案：把「求最值」翻译成「找边界」

34 题训练的「找第一个满足条件的边界」，真正的实战大舞台是二分答案（对答案做二分）——这里把桥梁搭好。「转化的原理」：一类最值问题直接求解很难，但「以答案为自变量」构造的验证函数是单调的——比如「吃香蕉的最小速度」：速度越快、耗时越少，「速度 k 能否在限期内吃完」是一个从假到真的单调阶跃（速度太小永远不行、足够大必然可行）——「最小的可行 k」就是「第一个满足验证的 x」，与 lower_bound 找「第一个 ≥ x」完全同构：34 题在「值域」上找边界，二分答案在「解空间」上找边界——这就是正文说「34 题是二分答案的预科」的全部含义。「模板的三要素」：一是答案空间的上下界——珂珂吃香蕉（875）的下界是 1、上界是各堆之和（一小时吃一堆都嫌多时就只能全量慢慢吃）；运送包裹（1011）下界是最大单件重量、上界是全部重量之和——上下界估得准，循环少跑一半；估错方向，直接全错；二是验证函数：875 的「按速度 k 算总耗时是否 ≤ h」、1011 的「按容量 c 算天数是否 ≤ D」——验证函数必须随 x 增大而单调放松，写反了整个二分失灵；三是循环骨架：求最小可行用「可行则右边界收到 mid、不可行则左边界迈过 mid」——这正是 lower_bound 的分支结构，mid 的取整方向必须与分支配套（向下取整配右边界收缩），「取整方向 × 分支方向」的配对错误是二分答案死循环的第一大来源。「死循环排查清单」（按命中率排序）：一查 mid 与分支是否配套——向下取整配「右边界收到 mid」安全，若分支写成「左边界收到 mid」就必须改用向上取整，否则两元素区间原地打转；二查循环不变量——左边界之前是否恒为「不可行」、右边界之后是否恒为「可行」；三查验证函数的边界——x 取上界时必须可行、x 取下界减一时必须不可行，否则答案根本不在区间里；四查「可行性单调」的前提——题目加了「不能拆分」「必须连续」之类的约束时，单调性可能被破坏，先想清楚再二分。「二分的本质条件」在此得到最终陈述：二分不要求「数组有序」，只要求「判定函数单调」——有序数组是「与元素比较」的单调特例，旋转数组是「局部构造判定」的单调，二分答案是「验证函数」的单调——三种场景共用同一副骨架。「工程里的二分答案」：限流器的最大通过速率（给定延迟预算反推容量）、容量规划（给定 SLA 求最小机器数）、灰度发布的步长选择（给定风险上限求最小批次）——凡是「验证一次的成本远小于枚举全部」且「可行域单调」的规划问题，都值得先问一句「能不能对答案二分」。练习路径建议：875 → 1011 → 410（分割数组的最大值，二分答案 + 贪心验证）——三题做完，「两个原子函数」就完成了从「数组技巧」到「通用思维工具」的跃迁。

小结

查找元素的两个位置的完整解析：两个原子函数（lower_bound——第一个 ≥ x、upper_bound——第一个 > x——「左闭右开」的模板——循环不变量：left 前全 < x、right 后全 ≥ x）；本题的组装（左边界 = lower_bound(target)、右边界 = lower_bound(target+1) - 1——「存在验证」——越界或值不等则 [-1,-1]）；变体家族的推导（四个变体全部由两个原子推导——「推导式记忆」）；工程贯通（时间序列的边界查询、数据库 B+ 树的范围检索——「这道题是数据库范围查询的理论基础。给学习者的建议：「边界二分」的练习要点是「循环不变量的维护」——每一步保证「left 前面全 < x、right 后面全 ≥ x」——「不变量」保证循环结束时 left 就是答案——「写循环时默念不变量」——以及，「lower_bound/upper_bound」的命名来自 C++ STL——熟悉 STL 的工程师应该知道 std::lower_bound 的存在——「标准库的函数」在工程中优先使用——「手写」是面试与理解，「调用」是工程——「两用」的正确姿势**。

查找第一个和最后一个位置，教会的是「用两个原子函数拼出所有边界查询」——从此二分边界不再靠背，靠的是「组合与推导」——「推导式记忆」是二分查找的最高境界。