在排序数组中查找元素的第一个和最后一个位置这道题我在 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 0right 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 1left 至少前进了一位当nums[mid] target时更新right midright 至少后退了一位。无论走哪个分支区间长度都在变小所以循环必然终止。如果再用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 题刚好是练习这套思维最好的入口。刷完这道题之后遇到再花哨的二分变体我都会先问自己三个问题目标下标满足什么单调条件搜索区间怎么定义每一轮迭代区间长度是否在缩小想清楚这三件事代码基本不会写错。