企业官网建设流程全解析

在排序数组中查找元素的第一个和最后一个位置这道题，我在 LeetCode Hot 100 的二分查找分类里刷到过很多次，面试也遇到过。它表面上是“在一个有序数组里找一个区间”，本质上考察的是二分查找里最容易被忽略的两件事：边界怎么约束，循环到底怎么收敛。很多朋友刷简单二分题能靠背模板混过去，一到这题就卡在 while 条件上，要么死循环，要么下标越界。今天我就把这题从头拆到尾，从最朴素的 O(n) 遍历一步步推到两次二分的写法，顺带把二分查找里那些“看起来简单、一写就错”的坑都翻出来讲清楚。适合正在刷 Hot 100、或者在准备面试但每次遇到二分变体都心里发虚的读者。

1. 题目背景与核心价值

1.1 题目回顾

题目给一个按非递减顺序排列的整数数组 nums，再给一个目标值 target。要求找出 target 在数组中出现的开始位置和结束位置，如果数组中不存在 target，就返回[-1, -1]。题目明确要求时间复杂度为 O(log n)。

题目看起来和普通二分查找差不多，但有一个关键区别：普通二分只要找到一个等于 target 的元素就可以直接返回；这题要找的是一个连续的区间，也就是至少得找到边界。如果数组中只有一个 target，那开始和结束位置自然相同；如果有多个连续的 target，边界之间就有一段长度。

举个例子：nums = [5,7,7,8,8,10]，target = 8，答案就是[3,4]。如果target = 6，因为数组里没有 6，返回[-1,-1]。

这个“找区间”的需求，加上 O(log n) 的时间限制，一下就把暴力扫描这条路堵死了。也正因如此，这道题成了二分变体题里的经典入门，掌握了它，后续很多偏门的二分变体都会顺很多。

1.2 为什么这道题值得反复刷

LeetCode Hot 100 里的题目，每一道都有它的定位。这道 34 题处于一个很微妙的位置：它不算最难的二分，但绝对是最容易让新手在边界上翻车的二分之一。

我自己的体会是，大部分人第一次写这道题都会经历三个阶段：

第一个阶段，直接循环找最左和最右。这个方案没问题，但是遇到最坏情况会退化到 O(n)，比如数组全部是同一个元素，循环会从两头一路扫到中间。

第二个阶段，意识到要用两次二分，但是写出来的二分不收敛。这是最常见的问题，比如在 while 条件里用了left <= right，结果返回的下标不停右移；或者把right = mid - 1和right = mid用混，导致越界。

第三个阶段，能写出一种稳定的模板，并且知道为什么这么写，面试时能把自己的“不变量”讲清楚。到这个阶段，这道题才算真正吃透了。

从面试的角度看，这道题经常被当作“二分查找的花式考法”，比如让你实现lower_bound、找插入位置、找峰值，核心思想其实就那么几个。把 34 题搞明白了，这些变体基本都能秒。

2. 解题思路拆解

2.1 为什么一次普通二分不够

先明确一个问题：为什么不能做一次完整二分，找到任意一个等于 target 的位置，然后向左右两边扩散？

这个方法在数据量不大的时候看起来没问题。但题目要求 O(log n)，扩散过程在最坏情况下是 O(n) 的。比如一个长度为十万的数组，里面全是同一个数字，任意二分的中间位置找到了 target 之后，向左向右各扩了五万个位置。虽然二分本身只用了 log n 次比较，但扩散这一步直接把复杂度拉回线性，等于白做了。

所以正确的方向是：利用有序数组的单调性，分别找左边界和右边界。左边界是“第一个等于 target 的位置”，右边界是“最后一个等于 target 的位置”。两次二分，每次都是 O(log n)，总复杂度仍然是 O(log n)。

2.2 把找区间翻译成找边界

二分查找里最难的地方，不是“找到目标”，而是“确定是哪一个目标”。因为数组里可能有多个重复元素，普通二分找到的可能是中间任意一个，而我们需要的是最左或最右的那个。

这里有一个很常用的等价转换：找 target 的右边界，可以转换成“找第一个大于 target 的位置，然后将下标减一”。也就是说，整个问题变成两个子问题：

• 找第一个大于等于 target 的位置（这个位置就是左边界候选）。
• 找第一个大于 target 的位置，它的前一个位置就是右边界候选。

这个方法看起来很绕，但好处是极其统一。只要你实现一个“找第一个不小于某个值的位置”的函数，左边界和右边界都能用它算出来，不需要分别维护两套逻辑。

很多语言的标准库里其实也已经封装好了这个概念。C++ 的lower_bound和upper_bound就是干这个的；Java 的Arrays.binarySearch虽然没直接提供，但它的返回值设计也和“插入点”相关。面试时虽然不能用现成函数，但思路完全可以借鉴。

2.3 区间模型与收敛原则

写二分之前，第一步必须先选定自己的区间模型。我用的是左闭右开区间，也就是[left, right)，约定 left 是可能答案的最小下标，right 是可能答案区间的右边界但不包含在内。初始时，left = 0，right = nums.length。

在这个模型下，二分循环用while (left < right)，循环结束时 left 和 right 一定相等。此时 left 就是我们要找的“第一个满足条件的位置”。

这个模型的好处是，循环每一轮都会实实在在地缩小区间。关键在于更新规则：

• 如果中间值满足条件，说明答案在 mid 或者 mid 左边，把 right 收缩到 mid。
• 如果中间值不满足条件，说明 mid 及 mid 左边都不可能是答案，把 left 推进到 mid + 1。

我第一次接触这套写法时，最不适应的就是right = mid而不是right = mid - 1。这一点恰恰是整个模板的灵魂：因为 right 本身是不包含在搜索区间里的，当nums[mid] >= target时，mid 可能是答案，所以 right 收缩到 mid，把 mid 保留在区间内。而 left 是包含在区间里的，所以当nums[mid] < target时，mid 已经被排除了，left 可以直接跳到 mid + 1。

理解了这个“保留候选”和“排除非候选”的区别，之后就不会再纠结该不该减一了。

2.4 找右边界时的对称思路

左边界的模板很容易套，但右边界如果再用“找第一个大于 target 的位置再减一”这种思路，很多人会在边界判断上晕。我更推荐直接用写左边界同样的思维，写一个对称函数：找“第一个大于 target 的位置”，然后减一。

这个对称函数和 leftBound 长得几乎一模一样，区别只有判断条件：

• nums[mid] > target时，收缩 right。
• nums[mid] <= target时，推进 left。

循环结束后，left 指向第一个大于 target 的位置，left - 1就是最后一个小于等于 target 的位置。因为题目已经确认 target 存在（左侧函数判断过了），所以left - 1就是右边界。

这种写法的好处是：两个函数结构完全一致，都满足同一个区间模型，不会出现“左边用一套、右边换一套”导致的混乱。

3. 代码实现与边界处理

3.1 Java 核心代码

下面是我最终采用的 Java 实现，整体结构清晰，两个辅助函数分别做一件事。

public int[] searchRange(int[] nums, int target) { int left = findLeft(nums, target); // 如果 left 越界，或者 left 位置的元素不是 target，说明数组里没有 target if (left == nums.length || nums[left] != target) { return new int[]{-1, -1}; } int right = findRight(nums, target); return new int[]{left, right}; } // 找第一个 >= target 的位置 private int findLeft(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid; } else { left = mid + 1; } } return left; } // 找第一个 > target 的位置，返回值再减 1 就是最后一个 <= target 的位置 private int findRight(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > target) { right = mid; } else { left = mid + 1; } } return left - 1; }

注意，这个 findRight 返回的是left - 1。我在实际给身边朋友讲这个代码时发现，最容易出问题的就是这里：为什么返回 left - 1，而不是直接返回 left？因为循环结束时 left 指向的是“第一个大于 target”的位置，而这个位置并不是 target 的区间，它前面的位置才是。由于前面已经确认 target 一定存在，所以 left - 1 一定在数组下标范围内，且一定等于 target。

3.2 三种边界情况的判定

写这道题时，我总结出了三种必须处理的边界情况，面试时如果能主动把这几类情况说清楚，会显得思路非常完整。

第一种，target 小于数组里所有元素。比如nums = [5,6,7]，target = 3。执行 findLeft 返回 0，但是nums[0] != 3，于是返回[-1,-1]。

第二种，target 大于数组里所有元素。比如nums = [5,6,7]，target = 9。findLeft 返回 3，此时left == nums.length，直接返回[-1,-1]。

第三种，target 在数值范围之间但数组里不存在。比如nums = [5,7,7,8,8,10]，target = 6。findLeft 返回 1，也就是第一个比 6 大的元素 7 的位置，但nums[1] != 6，返回[-1,-1]。

只要在 searchRange 开头做了这个“left 是否越界”和“nums[left] 是否等于 target”的判断，后面 findRight 的结果就可以放心使用，不需要再做额外的安全判断。

3.3 复杂度分析

时间上，findLeft 和 findRight 各自执行一次二分，每次二分把区间对半缩，所以时间复杂度是 O(log n)。空间上，只用了几个 int 变量，没有额外数据结构，所以空间复杂度是 O(1)。

这个复杂度也是这道题作为二分查找典型题的核心意义：它展示了在有序数据中，即使面对重复元素，也能用对数级别的时间完成复杂查询。

4. 实操过程中的典型问题

4.1 死循环是怎么产生的

我在给周围同学 review 代码时，发现二分查找死循环主要出在一个地方：更新 left 时用了left = mid，而不是left = mid + 1。

比如在找左边界时，如果nums[mid] < target，说明 mid 和它左边所有元素都比 target 小，mid 本身已经不可能是答案了。此时如果写成left = mid，那么 mid 这个位置又被放进下一轮搜索区间，而下一轮计算出的 mid 可能还是同一个位置，区间长度没有缩小，循环就卡住了。

要避免死循环，最核心的一点是保证每一轮迭代区间长度都严格减少。用左闭右开模型时，判断一下就能明白：当nums[mid] < target时，更新left = mid + 1，left 至少前进了一位；当nums[mid] >= target时，更新right = mid，right 至少后退了一位。无论走哪个分支，区间长度都在变小，所以循环必然终止。

如果再用left = mid这种写法，除非配合while (left + 1 < right)的模型，否则很容易卡死。所以我建议大家先固定一种写法，不要混用。

4.2 下标越界的根源

下标越界是这道题的另一个高发错误。常见的越界场景在 findLeft 的返回结果上：当 target 比数组所有元素都大时，left 会一路推进到 nums.length，这个值本身是合法的“插入点”，但如果你不去判断就直接访问nums[left]，必然越界。

另一个越界点出现在二分里面的 mid 计算。有些初学者写成int mid = (left + right) / 2，当 left 和 right 都很大时，两个 int 相加可能溢出，导致 mid 变成负数。稳妥的写法是left + (right - left) / 2，或者用无符号右移(left + right) >>> 1。

我在实际教学中见过一个很典型的错误：有人把 right 初始值设成了nums.length - 1，用的却是左闭右开的更新方式，于是 right 永远指向最后一个元素，整个逻辑全乱掉。选一个模型就自洽地用到完，这是二分题不出错的底线。

4.3 不同写法的选择

左闭右开（[left, right)）和左闭右闭（[left, right]）是两套主流二分模板，都能写对，但不要在同一个程序里交叉使用。

我本人更偏好左闭右开，原因有两个。第一个原因是和 C++ 的lower_bound语义对齐，日后看 STL 源码、写其他语言时不容易混淆。第二个原因是 right 初始值可以设为 nums.length，这个值是合法的越界位置，天然允许“如果目标比所有元素都大，可以返回数组长度”这种结果，省掉很多边界特判。

如果你更习惯左闭右闭，那 right 初始值就是 nums.length - 1，循环条件用left <= right，更新时得用left = mid + 1和right = mid - 1。这套逻辑也能写对，但需要注意：当 left 越过 right 时，left 指向的“插入点”和 nums.length 之间的关系需要额外想清楚。相比之下，左闭右开模板能从根上少掉一类边界特判。

4.4 Python 和 C++ 的写法差异

Python 写这道题时，基本逻辑和 Java 一致，但要注意列表下标和切片边界。这里给出一个参考实现：

def searchRange(nums, target): def find_left(): l, r = 0, len(nums) while l < r: m = (l + r) // 2 if nums[m] >= target: r = m else: l = m + 1 return l def find_right(): l, r = 0, len(nums) while l < r: m = (l + r) // 2 if nums[m] > target: r = m else: l = m + 1 return l - 1 left = find_left() if left == len(nums) or nums[left] != target: return [-1, -1] return [left, find_right()]

C++ 的话，除了手写也可以用 STL 的lower_bound和upper_bound，但说实话，如果面试是为了展示算法功底，我不推荐直接调库，还是要能手写。C++ 手写时和 Java 几乎一样，只需把数组访问换成 vector，注意nums.size()返回的是无符号数，和 int 比较时最好强制转换一下类型，这个细节也能避免一些隐式转换带来的麻烦。

Go 语言也是类似写法，切片和数组的边界处理基本一致，核心是理解模板本身。

5. 从这道题到二分查找的体系化

5.1 相关题型与刷题顺序

34 题掌握之后，可以按顺序刷下面几道题，它们和 34 题都有直接关联：

35 题搜索插入位置，本质就是 findLeft 的直接应用。给定一个排序数组和目标值，找不到 target 时就返回它将会被按顺序插入的位置。这个位置就是左边界模板返回的 left。

704 题二分查找是基础版，普通二分找到一个任意位置返回即可，比 34 题简单不少，适合预热。

33 题搜索旋转排序数组考察的是对有序数组旋转后的二分处理，需要先判断 mid 落在左半段还是右半段，再决定向哪边收敛。

153 题寻找旋转排序数组中的最小值，是另一种类型的极值搜索，核心在于判断中点和右边界的关系。

162 题寻找峰值，则跳出了有序数组的限制，利用的是“局部单调性”，但收敛的思路依然是二分的核心。

这些题做完后，再回头看你之前写过的二分代码，大概率会有一种“降维打击”的感觉：原来二分不是背 while 条件，而是设计不变量。

5.2 手写 lower_bound 的通用模板

基于 34 题，我把整套模板抽象成一条经验法则：找一个“最小下标 index，使得某个条件成立”，并且这个条件在数组上是单调的，那就一定可以用二分。

通用模板长这样：

int low = 0, high = nums.length; while (low < high) { int mid = low + (high - low) / 2; if (条件成立) { high = mid; } else { low = mid + 1; } } return low;

这个模板解决的是“是/否型”单调判断问题，也就是对某个下标 i，如果 i 满足条件，那么所有大于 i 的下标都满足；如果 i 不满足条件，那么所有小于 i 的下标都不满足。满足这种性质的查找，都能直接套模板。

34 题的 leftBound 就是这个模板加上了nums[mid] >= target这个条件；rightBound 则是把这个条件改成nums[mid] > target。把这个模板玩熟，以后再遇到“最大值的最小化”“最小值的最大化”这类更烧脑的题目，也能很快找到切入点。

5.3 面试时如何把自己的思路讲清楚

面试时写 34 题，不要一上来就闷头写代码。可以先跟面试官说清楚三个关键决策：

第一，为什么不能用线性扩散。说明最坏情况下会退化成 O(n)，不符合题目要求。这会让面试官知道你懂得分析复杂度，而不是只记住了答案。

第二，采用什么区间模型。这里你可以说“我用左闭右开区间，保持 left 是搜索区间的左端点，right 是右开边界，循环结束时 left 指向第一个满足条件的位置”。这句话非常重要，因为它展示了你的代码有明确的不变量。

第三，如何处理边界。可以先写 findLeft，再用 findLeft 的结果判断 target 是否存在，避免 findRight 里出现无效访问。这种顺序规划也能体现你的工程意识。

面试官后续如果追问，比如“如果数组里元素允许重复，你怎么找右边界”，其实就是引导你把模板说清楚；如果问“能不能一次二分搞定”，你也能用退化场景来解释为什么不行。这些都是加分项。

我个人在实际刷题和面试中的体会是，二分查找这一类题，最大的分水岭不在于题目难度，而在于你是否建立了“区间是什么、不变量是什么”的思维。34 题刚好是练习这套思维最好的入口。刷完这道题之后，遇到再花哨的二分变体，我都会先问自己三个问题：目标下标满足什么单调条件？搜索区间怎么定义？每一轮迭代区间长度是否在缩小？想清楚这三件事，代码基本不会写错。