面试里我经常用这道题当“二分查找试金石”给定一个非递减排序的整数数组 nums 和一个目标值 target要求返回 target 在数组中第一次和最后一次出现的下标如果不存在就返回 [-1, -1]并且强制要求时间复杂度是 O(log n)。大多数候选人都能在三分钟内写出普通二分查找但只要我补一个问题——“如果整个数组里全是同一个值左右边界怎么找”——不少人就开始拿命中的下标往两边线性扩散了。数组规模小的时候这个办法确实能骗过测试用例可一旦数据量上到百万级、目标值又恰好全部命中复杂度直接退化成 O(n)这道题考察的意义也就消失了。这个题在各类题库中通常排在 34 号左右是整个二分体系里最经典的边界题。它表面上只是把“找一个数”扩展成“找一个区间”中间隔着的那层思维跳跃恰恰是很多人背模板也背不出正确答案的原因为什么需要两次二分为什么两段代码长得几乎一样判定条件却一个是、一个是循环里差一个符号怎么就死循环或者漏边界这篇文章不打算只丢一份可提交的答案而是把题目背后的“为什么”全部拆开。先讲清楚问题本质再给出一套我自己实测很顺手的二分边界框架最后把边界用例、常见错误和延伸变体一起盘干净。适合刚学完普通二分、正准备啃边界题的人也适合那些刷过两三遍但还在硬背模板的同学。1. 先看这道题的真正考点不是“找目标值”而是“找分界点”1.1 普通二分为什么在这里不够用普通二分的退出条件是找到任意一个nums[mid] target的位置它从设计上就不区分“第一次”和“最后一次”。数组[1, 2, 2, 2, 2, 2, 3]里有五个 2普通二分可能返回第 1 个也可能返回第 5 个甚至返回中间任何一个下标全看 mid 怎么走。如果你在这个返回值上继续做文章就得知道这个命中位置到底在连续区间的哪一侧这本质上又变成了一个新问题继续往左还是往右搜索。所以第一层误区是“先用普通二分找到 target再往两边扩展”。往两边扫描的写法很直观但最坏情况正是我在开头说的那种全等数组。一百万个 2 排在那里你不管第一次命中在哪横向扩展最坏就是扫完一百万。数据规模一大O(n) 和 O(log n) 是几万倍的差距。1.2 另一种常见做法也很别扭找到命中点后对左右两侧分别二分这个思路看起来把复杂度救回来了命中点左侧用一次二分找左边界右侧用一次二分找右边界。但实现的时候要小心处理“已经命中”和“完全没有命中”两种分支代码会变得臃肿。而且你仍然要先写一次普通二分何况普通二分返回的命中点可能是区间内部的任意位置向左向右二分的边界初始化也要绕一下。这个做法能用但不是最优雅的思路。真正干净的做法是把题目整个重写一遍。1.3 把“找区间”重写成两个“找分界点”数组是非递减的目标值一旦出现等于它的所有元素一定聚在一起。我们不需要先知道任何一个命中位置只需要找这两个边界左边界第一个满足nums[i] target的下标右边界第一个满足nums[i] target的下标再减一。前者通常叫 lower_bound下界后者叫 upper_bound上界。如果你能求出来这两个值答案就直接拼装出来了。拿一个贯穿全篇的例子。假设nums [1, 2, 2, 2, 3, 5] target 2第一个 2的下标是 1第一个 2的下标是 4。于是左边界 1 右边界 4 - 1 3 答案 [1, 3]二次检查nums[1] 2命中结果正确。再试 target 4。nums中没有 4但 lower_bound 会返回下标 6表示数组末尾之后upper_bound 也返回 6右边界就变成 5。这时候左边界 6 大于右边界 5区间为空返回 [-1, -1]。这个视角的关键在于你只需要实现一个“找第一个满足条件的位置”的函数然后把不同条件塞进去。等于问题的复杂度没有变变的只是比较符号。2. 用两次二分把答案拼出来lower_bound 与 upper_bound 的正确形态2.1 手写 lower_bound寻找第一个 target的下标我用的是左闭右开区间[l, r)的模板初始时l 0r len(nums)。为什么右边取len(nums)而不是len(nums) - 1因为目标值可能比数组里所有元素都大这时正确答案就是“数组末尾之后”也就是下标len(nums)。这个位置必须在搜索区间里。def lower_bound(nums, target): l, r 0, len(nums) while l r: mid l (r - l) // 2 if nums[mid] target: l mid 1 # mid 本身不可能是左边界直接排除 else: r mid # nums[mid] targetmid 可能是左边界保留 return l逐行看这个函数的意图当nums[mid] target时mid 以及它左侧所有元素都小于 target不可能成为第一个 target的位置所以下一轮从mid 1开始当nums[mid] target时mid 有可能是候选答案但左边可能还有更小的下标也满足条件所以把右边界收缩到mid区间变成[l, mid)继续向左逼近。循环结束后l r这个位置就是第一个 target的下标。2.2 手写 upper_bound寻找第一个 target的下标和 lower_bound 几乎一模一样唯一的区别是把条件从 target换成 target。def upper_bound(nums, target): l, r 0, len(nums) while l r: mid l (r - l) // 2 if nums[mid] target: l mid 1 # mid 及左侧都不可能是第一个大于 target 的位置 else: r mid # nums[mid] targetmid 可能是第一个大于的位置 return l这里为什么用因为等于 target 的元素也要被排除。我们要找的是“严格大于”的第一个位置等于 target 的段仍然属于被划走的左半区。2.3 组装主函数检查一下返回区间是否有效得到两个边界后right 要用upper_bound(nums, target) - 1来换算因为 “最后一个等于 target 的位置”就是“第一个大于 target 的位置再往前一位”。def search_range(nums, target): left lower_bound(nums, target) right upper_bound(nums, target) - 1 if left len(nums) and nums[left] target: return [left, right] return [-1, -1]注意这里的判定只用检查nums[left] target。因为我们已经算出了 upper_bound如果存在 target[left, right] 必然是一个连续区间如果nums[left]不等于 target说明整个数组里根本没有 target。下面的例子可以验证nums [1, 2, 2, 2, 3, 5]target 4left 6但left len(nums)为假返回 [-1, -1]nums [1, 2, 3]target 0left 0nums[0] 1不等于 0返回 [-1, -1]nums [1, 2, 2, 2, 3]target 2left 1nums[1] 2返回 [1, 3]。2.4 使用语言内置函数渡劫和面试的差异如果你只是想快速解题编程语言自带二分边界函数可以直接用比如 Pythonfrom bisect import bisect_left, bisect_right def search_range(nums, target): left bisect_left(nums, target) right bisect_right(nums, target) - 1 if left len(nums) and nums[left] target: return [left, right] return [-1, -1]C 标准库里也有现成的 lower_bound 和 upper_bound但它们的返回值是迭代器最终区间长度用指针相减得到。但面试场景下我并不建议你上来就写内置函数。很多面试官会直接要求手写二分因为内置函数掩盖了你对边界收缩的理解。更实际的是内置的任意值查找函数在这道题上完全帮不上忙比如 Java 的Arrays.binarySearch只保证返回某个命中位置并不会告诉你是左边界还是右边界。我的经验是把这套手写模板练到肌肉记忆是不是用内置函数都只是顺手的事。3. 模板细节循环不变量、mid 取整与三种常见错误3.1 先把循环不变量刻在脑子里很多人背模板容易错是因为不知道每一行代码在维持什么约束。我习惯在写二分时心里默念两条约束区间[l, r)始终包含我们要找的“第一个满足条件的位置”nums[0..l-1]都不满足条件nums[r..n-1]都满足条件当 r 取到 n 时认为末尾之后也满足。以 lower_bound 为例l 左边的元素全部小于 targetr 右边的元素全部大于等于 target。循环开始时这个性质显然是成立的因为 l 0 左边没有元素r len(nums) 右边没有元素。每次迭代根据比较结果更新 l 或 r性质继续保持。当 l 和 r 撞在一起二者的性质叠加起来就得到结论nums[l]就是第一个大于等于 target 的元素。面试时如果能用这个框架把思路讲清楚比报一个模板名要有说服力得多。3.2 mid 向下取整和收缩方向必须配套否则死循环这是整个二分边界题最关键的细节。在while l r的左闭右开模板里mid (l r) // 2是向下取整。区间还剩两个元素时mid 会落在左边那个元素上。这时候只有两条分支分支一l mid 1l 至少前进一位区间缩小分支二r midr 至少后退一位区间缩小。也就是说这个模板里不存在l mid这种赋值。只要有人写了l mid同时 mid 又是向下取整区间还剩两个元素时就会原地打转。反过来你再看另一种对称模板要找“最后一个小于等于 target”的元素往往写成l mid作为一个分支这时 mid 就必须改成上取整(l r 1) // 2。看到循环里有l mid第一反应就是把 mid 取整方式换过来这是很多人在对称二分题上翻车的真实原因。我后来基本固定只用“向下取整 左边界加一”这一套就是为了减少大脑切换成本。3.3 三种一写就错但测试用例常常放过的细节第一种忽略-1。upper_bound 返回的是第一个严格大于 target 的位置你要的是“最后一个等于 target”的位置必须减一。我在初学时就犯过这个错nums [1, 2, 2, 2, 3]target 2好几个人会把答案写成[1, 4]多了一个位置。第二种把while l r记成while l r同时还在用r mid更新。这两种写法分别对应不同模板l r适合左闭右开区间l r适合左闭右闭区间且更新要换成l mid 1、r mid - 1。两套各学一半拼起来要么死循环要么返回错误下标。第三种在二分循环里遇到nums[mid] target就 return。上面讲过普通二分可以这样返回但这道题里命中位置没有任何区分度提前 return 相当于放弃了左右边界信息。正确做法是即使命中也要继续收缩区间。3.4 左闭右闭模板也能用但要注意对应关系如果你习惯了while l r的左闭右闭写法也能实现 lower_bound我把它写出来方便你对照def find_first_ge(nums, target): l, r 0, len(nums) - 1 while l r: mid l (r - l) // 2 if nums[mid] target: l mid 1 else: r mid - 1 return l循环结束时l 同样停在第一个 target的位置。区别仅仅在于把 r 收缩到mid - 1时区间是左闭右闭把mid已经排除掉了。这套写法也成立但它和左闭右开模板的收缩习惯不同容易混淆。我个人建议同一个人长期只练一种不要来回切。还有个顺手的小习惯mid 写成l (r - l) // 2而不是(l r) // 2。Python 里整数不溢出但不少语言里l r在极端场景是有溢出风险的写成减法形式更稳也不难记。4. 边界用例自查清单照着这张表测一遍基本就能确定代码没问题4.1 八组覆盖绝大多数边界的数据很多二分题不是死在主逻辑而是死在边界处理上。我整理了一张自测表建议写完代码后逐行过一遍输入数组targetlower_boundupper_bound预期输出这组数据在考察什么[]200[-1, -1]空数组不能让代码崩溃[1]101[0, 0]单元素命中[1]211[-1, -1]单元素未命中[1, 2, 3]000[-1, -1]target 小于所有元素[1, 2, 3]433[-1, -1]target 大于所有元素[1, 2, 2, 2, 3]214[1, 3]常规重复元素[2, 2, 2, 2]204[0, 3]全部都是 target[1, 3, 3, 5, 7]433[-1, -1]目标值落在两数缝隙中间最后两组尤其重要。[2, 2, 2, 2]这组是专门“打”那些靠向两边扩展的实现的[1, 3, 3, 5, 7]这种中间缺失的 target则检验你是否做了区间有效性判断。4.2 为什么最终判定只用检查 nums[left] 等于 target有人会疑惑left 和 right 是不是要一起判断才安全其实不用。我们已经限定 right upper_bound - 1。如果 target 存在所有等于 target 的元素在数组里是一个连续区间left 必然指向这个区间的第一个元素right 必然指向最后一个二者天然满足left right。如果 target 不存在left 可能等于 right 或大于 right但nums[left]一定不是 target甚至 left 可能直接等于 len(nums)。所以检查nums[left] target一个条件就够了。4.3 面试时怎么把推导过程说清楚面试不会只看代码对错还会看你能不能讲清楚边界逻辑。我建议按这个顺序表达先说明数组有序且等于 target 的元素在数组中形成一个连续子数组所以问题可以改成求这个连续子数组的左右端点左端点是第一个 target的位置右端点是第一个 target的位置减一两个二分全部基于“找第一个满足条件的位置”这个统一框架。讲到第三步时顺手在白板上画出那个贯穿例子[1, 2, 2, 2, 3, 5]指出 2和 2两个分界点面试官基本就能确认你是真懂不是背答案。5. 一道题撬动一组题同一个“分界点”框架的延伸用法5.1 常见的二分变体一张表搞定有了这套 lower_bound / upper_bound 之后很多看似独立的二分题都能直接套。下面的表我至今还在用遇到排序数组相关的需求先对照它转化一下需求等价写法返回值含义第一个 target的位置lower_bound(nums, target)可能是 len(nums)第一个 target的位置upper_bound(nums, target)可能是 len(nums)最后一个 target的位置upper_bound(nums, target) - 1可能是 -1最后一个 target的位置lower_bound(nums, target) - 1可能是 -1target 出现的次数upper_bound(nums, target) - lower_bound(nums, target)非负整数搜索插入位置lower_bound(nums, target)等价于要插入的下标看到没有你根本不需要为每个变体单独记一套模板只要会写 lower_bound 和 upper_bound其他全是在结果上做加减法和一次相等判断。5.2 我在实际项目里真的用到过这个框架有句话叫“排序数组二分只在考试里出现”其实不是。我有一个很具体的印象深刻的场景某个日志检索模块日志按时间戳从外部系统归并排序后落盘需要快速统计一个时间窗口内有多少条日志。最初版本直接遍历数组千万级日志每次查询都是线性时间明显扛不住。后来我把时间戳数组单独抽出来查询时就两句start bisect_left(timestamps, window_start) end bisect_right(timestamps, window_end) count end - start这背后的原理和这道题一模一样时间戳区间在有序数组里同样是个连续区间左边界做一次 lower_bound右边界做一次 upper_bound窗口内条数就是一减。查询从 O(n) 降到了 O(log n)而且没有引入任何复杂索引结构。算法题解和工程实践的边界有时候真的很薄。5.3 再往外延伸旋转数组、二维矩阵、字符串前缀这套“找第一个满足条件的位置”的思维还能继续扩展到很多问题。旋转排序数组里找最小值本质上是找第一个满足“比右侧最大值小”条件的位置只是比较条件变成了和右端点比较有序矩阵中查找目标经常可以退化成对每一行做一次 lower_bound甚至字符串数组里做前缀查找只要前缀具备单调性底层逻辑也是同一个二分。所以这道题值得反复练透不只为了通过一次面试还因为它能给后续一堆二分变体打底子。遇到新的题先盯住单调性和分界点不要一开始就追着“等于目标值”跑。最后分享一个我的个人习惯。每次复习二分我都会拿出[1, 2, 2, 2, 3, 5]target 分别取 0、2、4在纸上推演三个完整循环确认 left 和 right 的收缩过程。这个动作我重复了很多次直到后来不管用 Python 手写还是 C 写迭代器版本边界条件都不太需要动脑。如果你现在正好在理顺这一类题建议也把这个“推演三个 target”的小练习做一下坚持几周后二分边界就不再是玄学了。