企业官网建设流程全解析

面试里我经常用这道题当“二分查找试金石”：给定一个非递减排序的整数数组 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 = 0，r = 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] >= target，mid 可能是左边界，保留 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] > target，mid 可能是第一个大于的位置 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 = 4：left = 6，但left < len(nums)为假，返回 [-1, -1]；
• nums = [1, 2, 3]，target = 0：left = 0，nums[0] == 1，不等于 0，返回 [-1, -1]；
• nums = [1, 2, 2, 2, 3]，target = 2：left = 1，nums[1] == 2，返回 [1, 3]。

2.4 使用语言内置函数渡劫和面试的差异

如果你只是想快速解题，编程语言自带二分边界函数可以直接用，比如 Python：

from 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 左边的元素全部小于 target，r 右边的元素全部大于等于 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 + 1：l 至少前进一位，区间缩小；
• 分支二r = mid：r 至少后退一位，区间缩小。

也就是说，这个模板里不存在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 八组覆盖绝大多数边界的数据

很多二分题不是死在主逻辑，而是死在边界处理上。我整理了一张自测表，建议写完代码后逐行过一遍：

最后两组尤其重要。[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 面试时怎么把推导过程说清楚

面试不会只看代码对错，还会看你能不能讲清楚边界逻辑。我建议按这个顺序表达：

1. 先说明数组有序，且等于 target 的元素在数组中形成一个连续子数组；
2. 所以问题可以改成求这个连续子数组的左右端点；
3. 左端点是第一个>= target的位置，右端点是第一个> target的位置减一；
4. 两个二分全部基于“找第一个满足条件的位置”这个统一框架。

讲到第三步时，顺手在白板上画出那个贯穿例子[1, 2, 2, 2, 3, 5]，指出>= 2和> 2两个分界点，面试官基本就能确认你是真懂，不是背答案。

5. 一道题撬动一组题：同一个“分界点”框架的延伸用法

5.1 常见的二分变体一张表搞定

有了这套 lower_bound / upper_bound 之后，很多看似独立的二分题都能直接套。下面的表我至今还在用，遇到排序数组相关的需求，先对照它转化一下：

看到没有，你根本不需要为每个变体单独记一套模板，只要会写 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”的小练习做一下，坚持几周后，二分边界就不再是玄学了。