1. 为什么“老生常谈”的题年年都能难住一批人你要是去搜二分查找的面试题十份资料里有八份会提到“查找某个数字在排序数组中的起止下标”。这题常见的叫法有 Search for a Range也有叫 Find First and Last Position of Element in Sorted Array。题目本身很简单给一个升序数组比如 [1,2,3,3,3,5,7]让你返回数字 3 的第一次出现位置和最后一次出现位置也就是 [2,4]如果数组里没有这个数返回 [-1,-1]。没有重复值时更简单[1,3,5] 里找 3返回 [1,1] 就行。很多人觉得这题“背个模板就行”可真到了笔试或者项目里要手写时却经常在边界条件上翻车。要么返回的位置差一位要么死循环要么目标值不存在时返回了一个莫名其妙的下标。这篇文章我准备把这类问题的底层逻辑彻底拆开讲清楚“为什么普通二分在这里不够用”“边界二分到底在找什么”“不同位置的写法关键点在哪”最后给出一套可以直接用的代码方案和排查清单。1.1 普通二分法找的是“一个位置”不是“边界”普通二分查找的标准流程估计大家都能背设左右指针取中间下标比较中间值和目标值小于就把左指针挪到 mid1大于就把右指针挪到 mid-1相等就返回。这套流程解决的问题是“目标值存不存在”它不保证返回的是第几个匹配值。举个例子数组 [1,2,2,2,2,3]目标值是 2。普通二分第一次取 mid可能命中的是第三个 2也可能命中第一个 2这完全取决于数组长度和左右指针的初始位置。如果你只需要知道“有没有”这没问题可一旦需要知道“从哪开始到哪结束”普通二分的返回值就不够用了。我之前见过有人遇到这题先普通二分找到任意一个 2然后拿两个 while 循环左右扫把附近的 2 全扒出来。小数组测试全过一到大型评测直接超时。为什么因为如果整个数组全是 2左右扫描要做完整个数组复杂度退化成 O(n)二分查找的意义就完全没了。这个坑后面第五章会专门展开。1.2 边界问题的本质是找“属性发生改变的分界点”要找“第一次出现”本质是找第一个大于等于目标值的位置要找“最后一次出现”本质是找第一个大于目标值的位置然后再往前退一位。这两个目标都不是“等值搜索”而是“边界搜索”。边界搜索关心的不是“这个位置的值是不是 target”而是“从这个位置开始数组是不是进入了一个新的状态”。在升序数组里状态的分界点非常清晰在一串重复的 target 左边所有值都小于 target在右边所有值都大于 target。我们要找的就是“小于 target 的区域”和“等于 target 的区域”的交接以及“等于 target 的区域”和“大于 target 的区域”的交接。用生活里的例子类比一个小区每层有 10 户你问保安“门牌号从几号开始到几号结束都是空置房”。这不是找某一家而是找边界。边界问题天然适合二分因为你只需要判断中间位置处于哪个区域就能决定往哪半边继续找。1.3 先拆问题左边界和右边界分别是什么既然要分两次查找核心问题就变成两个独立的小问题左边界升序数组中第一个满足 nums[i] target 的下标 i。右边界升序数组中第一个满足 nums[i] target 的下标 i再减 1就是最后一个满足 nums[i] target 的下标。如果左边界下标越界或者左边界位置上的值不等于 target说明数组里根本没有这个目标值直接返回 [-1,-1]。把大问题拆成两个可复用子问题代码上最大的好处是每个函数只做一件事边界条件容易验证不会把自己绕晕。接下来的两章我会分别给出两套完整写法。2. 第一套写法上下界函数拆解工程中我最常用第一套方案先写两个基础二分函数一个叫 lower_bound找“第一个大于等于 target 的下标”一个叫 upper_bound找“第一个大于 target 的下标”。有了这两个函数最终查询只需要把它们的结果拼起来。2.1 下界和上界的定义必须对齐说代码之前先把术语对齐否则后面全乱。这里的 lower_bound 指“第一个不小于 target 的位置”即 nums[i] targetupper_bound 指“第一个大于 target 的位置”即 nums[i] target。注意upper_bound 返回的不是“最后一个匹配值”而是“最后一个匹配值的后一个位置”。这一点很多资料没有说清楚导致读者以为 upper_bound 返回的就是最右边那个 target结果调试半天对不上号。记住这个关系左边界 lower_bound(target)右边界 upper_bound(target) - 1如果左边界越界或者左边界位置的数不等于 target说明 target 不存在这个关系是所有解法的主心骨后面的代码都是它的具体实现。2.2 lower_bound 的代码与逐行拆解先给出最常用的左闭右开写法我用的是 Pythondef lower_bound(nums, target): left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid return left这段代码有几个关键点需要拆开讲。第一初始区间是 [left, right)也就是左闭右开。right 本身不参与取值它的含义是“边界可能在 right 这个位置”。左闭右开的优点是当数组长度为 1 时区间依然合法不会出现 left right 的困惑。第二循环条件用 left right 而不是 left right。因为在左闭右开区间里left right 表示区间为空空区间没有可查的元素循环自然结束。第三mid 取下取整。配合 left mid 1 的收缩方向不会死循环。如果有人把条件改成 while left right那初始 right 就要改成 len(nums)-1收缩规则也全变了两套东西不能混着用。第四判断条件看的是中点值是否小于 target。如果 nums[mid] target说明中点以及它左边的所有元素都不可能满足“ target”可以直接把左边界挪到 mid1。否则说明 mid 本身可能是候选位置也可能是 mid 右边有更靠左的候选所以把右边界收到 mid。因为右边是开区间right mid 不会丢掉 mid 这个候选值。函数结束后left 就是第一个不小于 target 的下标。如果数组里所有元素都小于 target它会返回 len(nums)也就是一个越界位置调用方必须判断。2.3 upper_bound 的代码与双函数组合upper_bound 和 lower_bound 几乎一样只有一个判断条件不同def upper_bound(nums, target): left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid return left这里的含义是只要中点值小于等于 target就说明中点以及它左边这一片都可能不是“大于 target”的区域左边界继续往右收缩只有中点值严格大于 target 时才把右边界收到 mid。最终 left 指向第一个严格大于 target 的位置。有了这两个函数完整区间查询可以这样写def search_range(nums, target): if not nums: return [-1, -1] left lower_bound(nums, target) if left len(nums) or nums[left] ! target: return [-1, -1] right upper_bound(nums, target) - 1 return [left, right]这段代码里面最值得强调的就是那句 if 判断。left len(nums)处理目标比所有元素都大的情况nums[left] ! target处理目标值在数组的值域范围内但实际不存在的情况。这两个检查缺一个都不行。我见过有人只写了越界判断结果目标值不在数组里时返回了一个“比 target 大的相邻数字”的位置看着像合法下标实际内容不对。2.4 target1 的小技巧以及它的限制上面这套代码里upper_bound 是单独写的。还有一个常见技巧是既然数组元素是整数查找“第一个大于 target 的位置”等价于查找“第一个大于等于 target1 的位置”。也就是说可以直接复用 lower_bound传入 target1left lower_bound(nums, target) right lower_bound(nums, target 1) - 1这个技巧在解题时非常简洁只需要维护一个二分函数。像 [1,3,5,5,7] 里查 5lower_bound(5) 返回 2lower_bound(6) 返回 4右边界就是 4-13正好是最后一个 5。但要注意这个技巧只适用于数组元素是整数、且 target 也是整数的情况。如果数组里存的是浮点数比如 [1.2, 3.5, 5.1]你没法保证 target1 意味着“严格大于 target”因为浮点数没有“紧挨着的下一个数”。遇到这类情况还是老老实实写一个独立的 upper_bound 函数用nums[mid] target来判断。这个限制在实际项目里经常出现尤其是处理时间戳、价格、分数这类带小数的数据时别踩进去。3. 第二套写法leftmost 和 rightmost 独立直写还有人喜欢不拆 lower_bound 和 upper_bound而是直接写两个函数一个找首次出现一个找末次出现。这两套本质上是一个数学关系但代码形态不同理解起来更直观。对初次接触这个题的人来说第二套写法反而更好上手。3.1 找第一次出现靠右收缩def first_position(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid return left if nums[left] target else -1这个函数用的是闭区间left 和 right 都指向真实存在的下标。核心逻辑是当 nums[mid] target说明 mid 及其左边都不可能是第一次出现的位置left 收缩到 mid1否则也就是 nums[mid] target说明 mid 有可能是候选right 收缩到 mid。为什么 right 收到 mid 而不是 mid-1因为 nums[mid] 可能正好等于 target如果收到 mid-1就把这个候选位置丢掉了。循环结束时 left right停在最靠左的匹配位置。最后判断这个位置上的值是不是真的等于 target不等于就返回 -1。这个函数假设数组非空。在使用前外层要做一次空数组判断否则 nums[left] 会越界。3.2 找最后一次出现mid 必须上取整def last_position(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right 1) // 2 if nums[mid] target: right mid - 1 else: left mid return left if nums[left] target else -1这个函数和前一个长得几乎一样区别有三个mid 变成了上取整判断条件变成 nums[mid] target收缩时用 right mid - 1 和 left mid。为什么 mid 必须上取整这是整个二分查找里最阴间的细节。因为在这个函数里当 nums[mid] target 时执行的是 left mid。如果 mid 取下取整当区间只剩两个元素时比如 left0、right1mid(01)//20nums[0] 恰好不大于 target执行 leftmidleft 变成 0和原来一样区间永远不会收缩程序直接死循环。所以需要 mid (left right 1) // 2让 mid 偏向右边那个元素。这样即使只剩两个元素mid1left1区间成功收缩。规律很简单循环里只要出现 left midmid 就必须上取整循环里只要出现 right mid 或者 left mid 1mid 就可以下取整。不用死记拿两个元素在纸上画一遍就知道了。3.3 人肉走查 [1,2,2,2,3,4,5] 找 2光讲理论容易飘拿一个具体例子完整走一遍。数组 [1,2,2,2,3,4,5]目标 2。先跑 first_position初始 left0right6mid3nums[3]2。nums[mid] target 不成立rightmid3。left0right3mid1nums[1]2。nums[mid] target 不成立rightmid1。left0right1mid0nums[0]1。nums[mid] target 成立leftmid11。leftright1循环结束nums[1]2返回 1。再跑 last_position初始 left0right6mid(061)//23nums[3]2。nums[mid] target 不成立leftmid3。left3right6mid(361)//25nums[5]4。nums[mid] target 成立rightmid-14。left3right4mid(341)//24nums[4]3。nums[mid] target 成立rightmid-13。leftright3循环结束nums[3]2返回 3。最终结果 [1,3]和预期一致。能看到第二次走查里 mid 每次都偏右这正是上取整的作用。如果你把那个 1 去掉第二次走到 left3、right4 时会死循环这是最容易验证的地方。3.4 两套写法怎么选第一套 upper_bound/lower_bound 拆分的好处是逻辑可复用。以后遇到“找第一个大于等于某个数”“找第一个大于某个数”的变体直接拿同一个函数改参数就行。做工程、处理有序数据定位区间时我更推荐这套因为它和标准库接口天然对应。第二套 first_position/last_position 的好处是语义直白读代码的人不需要理解 upper_bound 减一这种间接关系。面试手写时这套更不容易出边界遗漏。我的建议是日常刷题挑一套贴住形成肌肉记忆如果你想要一套能应对多种变体的通用模板选第一套。两套不要混着写否则最容易把区间口径搞乱。4. 边界用例验证把这 12 种情况跑通二分边界代码写完最怕的不是逻辑大错而是“看起来对但边界不对”。我自己每次写完二分都会固定过一遍下面这些用例基本能覆盖 90% 的坑。4.1 目标不存在的三种方向场景数组目标期望结果容易出的问题目标小于所有元素[1,5,8]0[-1,-1]返回 [0,?] 的假下标目标大于所有元素[1,5,8]9[-1,-1]lower_bound 返回 len越界访问目标在值域内但缺失[1,3,5,8]4[-1,-1]返回相邻值的位置第三种情况最容易漏。比如目标 4lower_bound 会返回 2nums[2]5如果不检查 nums[left] ! target你会返回 [2,?]看起来下标合法但根本不对。4.2 重复数据不同分布场景数组目标期望结果全数组都是目标[3,3,3,3]3[0,3]目标集中在开头[3,3,5,7]3[0,1]目标集中在末尾[1,3,5,5]5[2,3]目标稀疏出现[1,2,2,3,5,7]2[1,2]全数组都是目标这个用例对中心扩散方案来说是致命打击对二分方案则是最简单的场景之一。如果你写的代码在这个用例上明显慢说明肯定用了线性扫描要回炉重写。4.3 空数组、单元素、双元素空数组必须在函数入口直接返回 [-1,-1]因为后续所有 nums[left] 判断都会越界。单元素数组反而容易在循环条件上翻车。比如 [5] 找 5first_position 里 leftright0循环根本不进直接判断 nums[0]5返回 0。这个没问题。但如果代码写成 while left right且初始 rightlen(nums)就会访问越界。双元素数组是最容易暴露 mid 取整方向问题的。比如 [2,3] 找 2first_position 中 mid(01)//20没问题但 last_position 如果写成下取整left0、right1 时会停滞。所以每次写完单独用 [2,3]、[2,3,4] 这类小数组过一遍能省很多排查时间。4.4 构造极端样例验证性能除了功能正确还要验证性能。我建议构造一个长度为 10 万的数组里面所有值都是同一个数比如全是 7然后查 7 的范围。如果实现是真正的两次二分瞬间出结果如果用了中心扩散会明显卡顿甚至超时。这个用例也是面试时判断一个人是否真正理解二分边界的关键测试点因为光看代码不容易发现问题一跑性能测试就露馅。5. 常见问题与排查技巧实录5.1 返回值差一位这是二分边界最常见的错误症状是明明数组里有两个匹配值却只返回了一个或者左右边界刚好偏了一个位置。排查思路很简单先确认你是左闭右开还是左闭右闭然后用一个固定用例人肉走一遍。很多人写着写着就两种口径混用比如初始区间用左闭右开收缩时却写 right mid - 1结果每次排查少一个位置。我的经验是一个函数内部保持一种口径不要中途切换。左闭右开就统一用 right mid左闭右闭就统一用 right mid - 1别靠感觉微调。5.2 死循环二分代码最常见的死循环原因就是 mid 取整方向和收缩方式不匹配。我把关系整理成一张小表写之前扫一眼收缩方式mid 取整方向典型例子left mid 1 / right mid下取整first_positionleft mid / right mid - 1上取整last_positionleft mid 1 / right mid - 1上下取整均可普通二分判断如果你发现自己代码里同时出现 left mid 和下取整几乎必死循环。改法也很简单要么把 mid 改成上取整要么把 left 的收缩方式改成 left mid 1但要注意这可能会丢掉候选位置所以不是随便改的要结合目标判断。5.3 先找到一个值再向两边扩展复杂度的坑前面提到过“先普通二分再左右线性扫描”的方案我再展开说一下。这个方案的代码形态大概是这样# 看起来很对但会在重复数据上退化的写法 start binary_search(nums, target) if start -1: return [-1, -1] left start while left - 1 0 and nums[left - 1] target: left - 1 right start while right 1 len(nums) and nums[right 1] target: right 1 return [left, right]在目标值出现次数很少时这个方案跑得飞快所有测试都能过。可一旦所有元素都是 target比如一个 10 万元素的数组全是 3左右 while 会各扫 5 万个元素整体时间复杂度从 O(log n) 恶化成 O(n)。二分题考的就是“能不能在对数时间解决”这个方法等于直接宣告失败。更让人头疼的是这个方案在单元测试阶段不容易被发现因为常规测试数据不会刻意构造全等数组。所以以后看到“二分 线性扩展”的组合第一反应就应该是警惕。5.4 空数组和溢出细节空数组是老生常谈但总有人漏。search_range 入口最好第一行就写 if not nums: return [-1,-1]。另外还有一个很多语言里才会出现的细节mid (left right) // 2 在 C 或 Java 里可能溢出因为 leftright 如果超过整数上限结果会变成负数。更稳妥的写法是 mid left (right - left) // 2或者用无符号右移。Python 里整数没有溢出问题所以我平时写 Python 代码会用简单形式但如果你用别的语言实现建议养成写 left (right - left) // 2 的习惯。5.5 一套万能调试清单我每次写完二分边界代码都会按这个顺序自查循环条件写的是 left right 还是 left right和初始区间是否一致。mid 取整方向是否和收缩方式匹配。目标值不存在时会不会访问非法下标。数组为空时会不会在函数入口被拦截。返回值在语义上是“下标”还是“插入位置”。只要这五条全对代码基本不会出大问题。6. 从“查找一个数的区间”扩展出去这套思想能做的事这道题看起来只是一道经典面试题但它背后的“边界二分”思想可以复用到很多场景。这里列几个我实际遇到过或者经常用到的扩展方向。6.1 统计出现次数区间求出来之后出现次数就是 right - left 1前提是目标存在。这是“查找区间”最典型的实际用途。比如一个日志服务里要统计某条错误码在一段时间内的出现次数如果原始数据的时间戳是有序数组用这个模板定位起始和结束位置一减就出来比遍历全表快得多。这个场景在数据检索、监控告警、统计分析里都很常见。6.2 找第一个大于 target 的元素这个其实就是 upper_bound 本身。代码和 lower_bound 几乎一样只是把判断条件从 nums[mid] target 改成 nums[mid] target。如果 target 不在数组中它返回的就是第一个大于 target 的位置如果 target 存在则返回最后一个匹配位置的后一个位置。这个能力在有序数组插入、区间合并、二分查找旋转数组里的分界点时非常有用。6.3 标准库 bisect 怎么对应如果你在做工程而不是刷题Python 标准库的 bisect 模块直接提供了现成实现import bisect left bisect.bisect_left(nums, target) right bisect.bisect_right(nums, target) - 1对应关系是标准库函数返回内容对应本文函数bisect_left(nums, target)第一个 target 的位置lower_boundbisect_right(nums, target)第一个 target 的位置upper_bound真正做工程时直接用标准库是明智的因为它经过海量验证比自己手写少操心而且同样 O(log n)。但面试、笔试或者理解原理时手写依然是基本功。等你看懂了本文第一套写法再去看 bisect 源码会发现没有任何神秘感内部做的完全是同一件事。6.4 旋转有序数组的边界查找旋转有序数组也叫循环有序数组典型题是“在一个发生过旋转的升序数组中查找目标值”。它的核心思路仍然是找分界点数组从哪个位置开始重新恢复升序。这里的二分判断条件不再是 target而是“nums[mid] 和 nums[left] 或 nums[right] 的大小关系”。理解了边界二分里“找属性改变点”的思想再去看旋转数组会顺利很多因为那里同样是找“分界”只是分界的属性变成了“是否存在旋转”。7. 写在最后的实操体会二分查找这类题目模板背熟不难真正难的是搞清楚每次收缩时候选区间里哪些元素可以丢、哪些不能丢。丢错了结果就差一个位置没丢但方向错了又可能死循环。每次写之前问自己三个问题当前区间是左闭右开还是左闭右闭mid 是上取整还是下取整目标不存在时返回什么只要这三件事想清楚不管是查找一个数的区间还是查找旋转数组的分界都不容易再出幺蛾子。如果你准备面试建议把 lower_bound、upper_bound、first_position、last_position 四个函数各默写三遍默写时把每一步为什么这么收缩写在注释里而不是只抄代码。如果你做工程建议把 bisect_left 和 bisect_right 的语义吃透日常开发直接调标准库把省下来的时间花在真正复杂的数据业务逻辑上。最后再分享一个小技巧写完类似函数后用[1,2,2,2,3,4,5]这个标准样例人肉走一遍再把目标依次换成 0、2、3、9看输出分别是 [-1,-1]、[1,3]、[4,4]、[-1,-1]。这四个结果只要全对你的代码就基本稳了。我踩过几次边界差一位的坑之后现在每次都用这套自检样例再也没在二分边界上翻过车。