手撕二分查找：边界条件与循环不变量详解

面试遇到手撕代码环节很多时候面试官会顺手出一道“实现二分查找”。你别觉得这是送分题我这些年筛简历、带新人、组织模拟面试亲眼看过太多人在这个入门级题目上翻车——要么边界条件想不清楚要么 mid 算到一半越界要么循环条件写错直接死循环。能一次写对、不越界、不死循环的人十个里未必有三个。二分查找这个东西表面看是几行循环实际上它考的是你对区间不变量的理解、对边界条件的敏感度、对代码精确性的追求而这些恰恰是工程能力和算法功底最真实的剪影。这篇文章我就把自己整理的一套“手撕二分查找”心得完整写出来从最基础的查找指定值开始到查找上下界、查找插入位置、二分答案、浮点数二分再到现场面试的书写顺序和自测对拍方法全部串起来。不管你是刚刷题的学生还是准备跳槽的工程师还是单纯想把自己的基础打扎实这篇文章都值得你反复看几遍最好能跟着代码自己敲一遍。1. 手撕二分查找前先想明白这题到底在考什么很多人上来就背模板背完就忘换个问法就不会做。原因在于没有理解二分查找背后的逻辑本质只是把几行代码当“口诀”记了。先把这个底层逻辑想透后面所有变体你都可以自己推出来而不是靠记忆。1.1 为什么“简单的二分”会难倒一大片人二分查找的原理确实简单在一个有序数组里找目标值每次取中间元素和目标比较根据大小关系把搜索区间砍半复杂度从 O(n) 降到 O(logn)。这个思路小学生都能听懂但一到写代码就暴露问题。核心难点不是“二分”这个思想而是你到底维护的是一个什么样的区间以及每次缩小区间时边界到底要不要带上 mid 本身。我拿一个最常见的问题举例。假设你要在数组[1, 3, 5, 7, 9]里找目标值 7。大部分人能写出类似这样的骨架left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1这段代码看起来没问题但注意一个细节我写的是left right而如果我把循环条件改成left right代码行为就完全变了。为什么因为对应的是“闭区间”语义对应的是“半开区间”语义。你脑袋里想的是哪一种区间循环条件、左右边界的更新方式都必须跟哪一种区间严格配套。混着来轻则漏查一个元素重则死循环。类似这样的细节才是手撕二分真正考察的东西。面试官不是不知道你会二分他是想看你在压力下能不能保持逻辑的一致性。所以这篇文章我强调的第一件事就是写二分查找之前先在内心里把区间定义说清楚。1.2 循环不变量手撕代码时最该写进注释的一句话“循环不变量”这个名词听起来很高深其实说白了就是一句话每一轮循环开始的时候你要找的目标值位于哪个区间内。假设我采用“左闭右闭”的写法即left和right都指向数组内真实存在的下标那么我的循环不变量就是目标值 target 如果存在一定位于[left, right]这个闭区间内。初始时left0, rightlen(nums)-1覆盖整个数组。只要这个不变量成立我每次比较完nums[mid]和target之后就可以放心地缩小范围如果nums[mid] target说明 target 在 mid 右边那我把left挪到mid1新区间[mid1, right]依然包含 target如果nums[mid] target就把right挪到mid-1新区间[left, mid-1]也依然包含 target。每轮区间都在缩小最终要么找到要么区间变空表现为left right此时就可以确认 target 不存在。我在面试手撕的时候习惯先把这段不变量用注释写在代码上方。一方面它帮我自己理清逻辑另一方面面试官一眼就能看出你不是在背代码而是真正理解了你维护的是什么。这是一个非常加分的细节比闷头敲一堆代码有用得多。2. 基础款查找指定值的两种区间写法及边界处理这一节我们把最基础的“在有序无重复数组中查找指定值”做到极致。我会把两种区间写法都摆出来并且讲清楚它们之间的区别和使用场景。建议你把两种写法都练熟因为它们分别对应后续变体问题中两种不同的思维路径。2.1 左闭右闭写法最容易理解也最常用先看经典写法def binary_search(nums, target): left, right 0, len(nums) - 1 # 区间 [left, right]闭区间 while left right: # 区间不为空 mid left (right - left) // 2 # 防止 left right 溢出 if nums[mid] target: return mid elif nums[mid] target: left mid 1 # target 在右半边mid 已经被排除 else: right mid - 1 # target 在左半边mid 已经被排除 return -1 # 区间为空说明 target 不存在这个写法的关键在于while left right。因为闭区间的语义是“区间内所有下标都可能是答案”所以当left right时区间里还有一个元素没检查必须再进一轮循环。此时如果nums[mid] target直接返回如果不等left会变成mid1或right变成mid-1区间空掉循环结束。另外注意mid left (right - left) // 2。在 Python 里直接(left right) // 2通常也没事因为 Python 的整数没有固定位数限制不会溢出。但在 C 或 Java 里如果left和right都接近2^31-1相加就可能超过 int 上限产生负数或者错误的 mid。写成left (right - left) // 2是从根上杜绝这个问题。面试官很爱问这一句答得上来说明你有实际工程经验。2.2 左闭右开写法STL 和很多底层库的默认选择再来看看半开区间写法也就是[left, right)def binary_search(nums, target): left, right 0, len(nums) # 区间 [left, right)right 不包含 while left right: # 区间不为空 mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 # 新区间 [mid1, right) else: right mid # 新区间 [left, mid) return -1半开区间和闭区间最大的区别在于right的初始值和更新方式。因为right本身不指向有效元素所以初始值设为len(nums)循环条件变成left right。当left right时区间已经空了不需要再循环。更新时如果target nums[mid]说明右边界应该是mid因为mid不是目标而区间又是左闭右开的right mid就能把mid排除在搜索范围外同时不丢任何左边的元素。很多语言的标准库底层就是基于这种写法实现的。比如 C 的lower_bound、upper_boundJava 的Arrays.binarySearch内部逻辑都和半开区间高度相关。原因在于半开区间在处理“插入位置”“上下界”这类问题时代码更自然可以干净地返回一个指向第一个不满足条件元素的位置。我建议你把半开区间写法作为默认习惯去练因为它能直接平滑过渡到下一节要讲的所有变体。2.3 两种写法的对比与选择建议对比维度左闭右闭 [left, right]左闭右开 [left, right)初始值left0, rightlen(nums)-1left0, rightlen(nums)循环条件left rightleft rightleft 更新mid 1mid 1right 更新mid - 1mid循环结束时区间left rightleft right适用变体查找精确值查找上下界、插入位置我的建议是精确查找指定值闭区间写起来更直观适合新手查找边界、插入位置半开区间更顺手适合作为长期默认模板。但无论选哪种每次写之前都要像念咒语一样默念一遍自己的区间不变量然后让循环条件和边界更新全部服从这个不变量。3. 高频变体查找边界与插入位置刷题刷到一定阶段你会发现二分查找极少直接考“找某个值”更常见的是这些变体找到 target 第一次出现的位置找左边界找到 target 最后一次出现的位置找右边界找到第一个大于等于 target 的元素位置lower_bound找到第一个大于 target 的元素位置upper_bound找到最后一个小于等于 target 的元素位置给定插入位置使数组依然有序这些问题表面上是“查找”本质上都是在研究边界。边界问题恰恰是最容易写错的地方。下面我用统一模板来拆解。3.1 统一模板用 lower_bound 和 upper_bound 打天下我先给出两个极其重要的基础函数。理解它们之后你会发现上面那一串问题全是它们的组合。def lower_bound(nums, target): 返回第一个 target 的元素下标如果不存在返回 len(nums) left, right 0, len(nums) # [left, right) while left right: mid left (right - left) // 2 if nums[mid] target: right mid # 区间收缩到 [left, mid) else: left mid 1 # mid target排除 mid return left # left right都是答案 def upper_bound(nums, target): 返回第一个 target 的元素下标如果不存在返回 len(nums) left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 # mid target继续向右找 else: right mid # mid target向左收缩 return left这两个函数都基于半开区间[left, right)循环结束时left right返回值可以直接作为“插入位置”。这是它们最优雅的地方。拿lower_bound举例裸数组[1, 3, 3, 5, 7]target3运行过程大致是初始 left0, right5mid2nums[2]3满足 3所以 right2区间 [0,2)mid1nums[1]3满足条件right1区间 [0,1)mid0nums[0]1不满足条件left1区间为空leftright1返回 1也就是第一个 3 的下标同样upper_bound(nums, 3)会返回 3因为第一个大于 3 的元素是下标 3 处的 5。那么upper_bound - lower_bound就直接算出了 target 在数组中出现的次数。3.2 由两个 bound 组合出的常见答案这一小节直接给结论遇到题目就能套需求代码第一个等于 target 的位置lower_bound(nums, target)再判断该位置是否等于 target最后一个等于 target 的位置upper_bound(nums, target) - 1再判断该位置是否等于 targettarget 出现的次数upper_bound(nums, target) - lower_bound(nums, target)第一个大于等于 target 的位置直接lower_bound(nums, target)第一个大于 target 的位置直接upper_bound(nums, target)最后一个小于等于 target 的位置upper_bound(nums, target) - 1在有序数组中插入且保持有序的位置直接lower_bound(nums, target)举个例子如果要找数组[2, 2, 2, 4, 5]中 2 的第一次和最后一次出现位置lower_bound(nums, 2)返回 0upper_bound(nums, 2)-1返回 2一次多好。你只需要把两个 bound 函数背熟、理解透绝大多数二分边界题都不需要现场重新推导。3.3 变体最容易踩的坑变体题写错绝大多数都错在“到底哪些元素要保留哪些要排除”。我见过特别多的错误版本比如手写lower_bound时把判断条件写成if nums[mid] target: right mid这样看起来也对但你得额外处理找不到 target 的情况而用就不用。再比如upper_bound写完之后忘记返回值可能等于len(nums)直接拿它当下标访问数组就会越界。还有一个非常隐蔽的坑要找“最后一个小于等于 target 的元素”时不要自己新写一个搜索直接用upper_bound(nums, target) - 1就行。有人会想我能不能在循环里直接维护“最后满足条件”的位置能但代码很容易写成left mid一旦处理不好就是死循环。因为二分查找里最忌讳的就是left mid这种赋值方式它可能导致区间无法缩小。下面我专门讲这个死循环问题。4. 最容易写死循环的地方区间收缩的代价二分查找并不难但“死循环”三个字能让再简单的问题变得棘手。尤其是当你想在循环内保留 mid 而不是排除 mid 的时候很容易陷入无限循环。这一节我把它彻底讲透。4.1 为什么left mid会死循环先看一个典型的错误代码目标是找“最后一个小于等于 target 的位置”def last_less_equal(nums, target): left, right 0, len(nums) - 1 ans -1 while left right: mid (left right) // 2 if nums[mid] target: ans mid left mid # 试图保留可能的下一个位置但这里很危险 else: right mid - 1 return ans如果数组只有[1, 2]target2初始 left0, right1mid0因为nums[0]1 2所以 ans0leftmid0。注意left没有变化仍然是 0下一轮循环 left0, right1mid0再做一遍一模一样的比较……死循环诞生了。原因在于当mid已经被判断为满足条件后如果你直接把left设为mid而mid又恰好等于left搜索区间根本没有收缩。二分查找必须保证每一轮循环都会缩小搜索范围否则算法就不是对数复杂度而是直接跑死。4.2 安全写法永远让边界“排除” mid修复上面的问题思路很简单每轮比较完后mid 必须被排除出新的搜索区间。对于左闭右闭区间更新方式只能是left mid 1或right mid - 1对于左闭右开区间更新方式是left mid 1或right mid。这两种方式都能保证区间长度严格减小因为当mid被排除后新区间至少比原区间少一个元素。继续用半开区间写“最后一个小于等于 target 的元素”def last_less_equal(nums, target): # 等价于 upper_bound(nums, target) - 1 left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 # mid 已经检查过排除它 else: right mid # mid 是第一个 target 的位置收缩 return left - 1 # left-1 是最后一个 target 的位置这样的写法从结构上消灭了死循环的可能。我再说一遍如果你写的更新里出现了left mid那 99% 的情况下要回头检查。除非你非常清楚自己在做什么、并且配合了额外的退出条件否则这就是死循环的温床。4.3 mid 的取整方向也有讲究另一个和死循环密切相关的细节是mid的计算取整方向。对于整型二分mid left (right - left) // 2是向下取整。在半开区间[left, right)下如果区间长度是 1mid 就等于 left此时配合left mid 1或right mid区间都会变小没问题。但如果你改写了left mid这种模式又恰好用向下取整就可能出现区间永远停在长度为 1 或 2 的情况。反过来如果某个算法模板里要求用右中位数也就是mid left (right - left 1) // 2那它通常是为了配合别的边界更新方式。看到“向上取整”的 mid 计算不要慌先看它对应的边界收缩方式通常和左闭右闭 left mid的场景配套出现。比如查找“最后一个小于 target 的元素”有些人就用这种写法因为它能防止 left 卡住不动。不过我的建议是不要迷信各种花哨模板认准一种不会死循环的写法把逻辑推清楚然后所有的题都用同一套思维去解。这套思维就是维护一个包含所有“潜在答案”的区间每轮把 mid 排除掉保证区间严格收缩。5. 面试现场的手撕策略从拿到题目到通过测试手撕二分查找这件事和平时刷题不太一样。面试时你有时间压力、有面试官盯着、还有白板或者共享文档的限制。我下面分享一套我验证过很多次的现场流程照着走基本不会乱。5.1 先确认需求再写代码拿到题目第一件事不是写是问。面试官说“实现一个二分查找”我会立刻反问三连数组是升序还是降序有没有重复元素要找的是任意一个下标还是第一个/最后一个满足条件的下标如果找不到返回什么是 -1还是插入位置这三个问题直接影响模板选择。比如升序无重复元素用精确查找模板升序有重复元素且要找边界用 lower_bound/upper_bound 模板找不到要返回插入位置直接用 lower_bound。你把这些确认完面试官会认可你的工程思维后续写代码也更有底。5.2 在注释中写出区间不变量然后按步骤展开我强烈建议你在面试白板上把代码组织成这个顺序先用一行注释写明区间不变量比如# 搜索区间 [left, right)left 是第一个可能的位置初始化 left 和 right写循环条件写 mid 的计算并顺手注释为什么不用(leftright)//2按条件分支收缩区间每一行都确保 mid 被排除返回之前先想清楚边界情况比如数组为空、target 比所有元素都大/小以 lower_bound 为例面试版代码可以写成def lower_bound(nums, target): # 不变量目标插入位置在 [left, right) 内 left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: right mid else: left mid 1 return left写完代码后不要直接说“写完了”自己口头跑一个简单例子。比如[1, 3, 5]target2手动模拟一遍确认返回 1插入位置。这个“自测”动作很加分能让你在正式测试前就把明显的逻辑漏洞补上。5.3 至少准备 6 组测试用例无论面试还是平时刷题二分查找的用例设计都有一套固定套路我把它总结成一个清单空数组比如[]直接验证边界单元素数组比如[5]target 分别取 3、5、7验证左右边界和命中两元素数组比如[1, 2]target 取 1、2、0、3这四个值最容易暴露死循环所有元素都相等的数组比如[2,2,2,2]target2验证第一个和最后一个位置的查找长度很大且 target 在首尾的数组比如list(range(1000000))target0 和 999999一对相邻值比如[1,2,3,4,6,7]target5验证找不到时返回插入位置的行为这套用例能把你写的二分代码从“看起来对”变成“大概率真对”。尤其是那个[1,2]的例子配合 target0 或 3几乎能把所有边界和死循环问题都钓出来。6. 用对拍暴力解法验证二分正确性面试可以靠手动用例但平时训练我建议你学会“对拍”。所谓对拍就是写一个最笨、最容易验证正确性的解法再写一个你要测试的优化解法然后随机生成大量测试数据比较两个解法的结果是否一致。这是保障算法代码正确性最有效的手段没有之一。6.1 对拍代码怎么写以验证 lower_bound 为例暴力解法就是线性扫描整个数组找到第一个 target的元素下标import random def brute_lower_bound(nums, target): for i, val in enumerate(nums): if val target: return i return len(nums) def test_lower_bound(trials10000): for _ in range(trials): size random.randint(0, 20) nums sorted(random.randint(-100, 100) for _ in range(size)) target random.randint(-120, 120) # 允许重复元素所以必须全部测 res_brute brute_lower_bound(nums, target) res_fast lower_bound(nums, target) if res_brute ! res_fast: print(出错了, nums, target, res_brute, res_fast) return print(全部通过)跑个 10000 次随机测试如果全部通过基本可以确认你的 lower_bound 实现是正确的。这个方法论在做所有二分变体题的时候都通用。比如你要写“查找最后一个等于 target 的位置”那暴力版就倒着线性扫描找到第一个等于 target 的下标然后随机生成含重复元素的有序数组对拍它个几万次。6.2 对拍里几个容易踩的细节随机数据要包含重复元素。二分边界题的很多隐藏 bug 都只在重复元素下暴露。生成数组时不要用set去重。target 的范围要超出数组元素范围。比如数组元素范围是 -100 到 100那 target 就选 -120 到 120强制测试 target 小于所有元素、大于所有元素的情况。数组大小要覆盖 0、1、2、3 这些极小规模。我通常会这样生成size random.randint(0, 5)和size random.randint(6, 30)各跑一半保证小规模边界被覆盖。循环次数不要太少。10000 次基本够如果是特别容易出错的变体我会跑 100000 次。跑一次也就几秒钟安全性高得多。对拍的价值不只是验证“当前版本正确”还能在你日后修改边界策略时迅速判断改动是否引入了新 bug。我现在的习惯是每写一个二分变体函数就顺手在文件里保留一个暴力版配合随机测试。这种习惯帮我挡掉了大量肉眼看不出来的问题强烈建议你也试试。7. 二分不止于数组二分答案与浮点数二分二分查找的威力远不止在数组里找数。当你发现某个问题的答案具有“单调性”——即答案越大或越小可行性呈现规律的转变——就可以用二分来逼近答案。这就是“二分答案”。刷题到一定阶段你会频繁遇见它。7.1 二分答案是什么什么时候用举个例子给你一堆绳子的长度要求切出 k 条长度相同的绳子问每段最长能有多长。这个问题不是让你在数组里找目标值而是让你“猜一个答案”然后检查这个答案可不可行。这里的关键性质是如果某段长度 x 可行能切出至少 k 条那么比 x 更小的长度也一定可行。也就是说可行性关于长度是单调变化的这是二分答案的典型信号。特征词非常明显“求最大中的最小”“求最小中的最大”“答案在某个范围内且答案越大越难满足”等。只要你发现了单调性就可以把答案当成搜索区间里的 target用二分的思路快速逼近最优解。7.2 整数二分答案的模板沿用半开区间的思想求“满足条件的最小值”可以这样写def feasible(x): # 根据题目判断每个候选答案 x 是否可行 pass def min_feasible(lo, hi): # 答案范围 [lo, hi]求最小可行值 left, right lo, hi 1 # 半开区间 while left right: mid left (right - left) // 2 if feasible(mid): right mid # mid 可行继续找更小 else: left mid 1 # mid 不可行排除 return left # 最小可行值这里唯一的额外要求是你要根据题目的数据范围确定 lo 和 hi并确认可行解一定存在于这个区间内。比如绳子切段问题lo0hi最长绳子的长度答案肯定在这个区间里。剩下的逻辑和 lower_bound 如出一辙连边界更新都不用改。掌握这个模板等于把二分答案题都归入了“套模板 写 feasible”两步流程。7.3 浮点数二分别再用 EPS 死磕循环了浮点数二分和整数二分长得像但有一个重要的实践差异不要依赖一个很小的 EPS 来终止循环。很多人会写while right - left 1e-6听起来很严谨但 EPS 选多大很纠结——选大了精度不够选小了可能循环次数过多甚至因为浮点误差永远不收敛。稳妥做法是固定迭代次数。比如用浮点二分求平方根def sqrt_binary(x): if x 0: return 0 left, right 0.0, max(1.0, x) # 注意 x 小于 1 时平方根比 x 大 for _ in range(100): # 100 次迭代足够精度到 1e-15 以上 mid (left right) / 2 if mid * mid x: left mid else: right mid return (left right) / 2这里我没有用while right - left eps而是固定迭代 100 次。为什么因为浮点数二分每轮会把区间长度减半100 轮之后精度远高于日常需求同时完全避免了“EPS 设太小导致死循环”的问题。注意x小于 1 时比如 0.25 的平方根是 0.5大于 x 本身所以右边界至少要取到 1.0不能直接设成 x。这种小陷阱只有在实测中才会发现。8. 手撕二分这段路我踩过的坑和后续更新的方向二分查找这个东西看十遍不如亲手写一遍写一遍不如对拍一万遍。我最初带新人时经常看到他们背模板背得滚瓜烂熟但稍微改一下题目条件就露馅。后来我把训练方式改成“先自己推一遍再随机对拍”效果立刻好了很多。这套方法我在自己准备面试时也反复用过是真能提升手撕能力的。我把自己踩过的坑再集中列一下你写代码时对照着看循环条件还是取决于你脑子里想的是闭区间还是开区间。千万别混用最好全篇统一用半开区间。mid计算用left (right - left) // 2而不是(left right) // 2。后者在 C/Java 里可能越界。边界更新必须排除 mid。尽量不用left mid否则要仔细推死循环条件。找不到的时候返回什么必须和面试官确认。是 -1、插入位置还是 len(nums)直接影响答案正确性。浮点二分别用 EPS固定迭代次数。每次手撕完用小用例自测一遍。特别是[1,2]、空数组、全相同数组这三类用例。这个主题我自己也在持续更新后续还想再写几篇相关的内容比如在二维有序矩阵中做二分、在旋转有序数组中查找目标值、以及如何用二分思想优化动态规划状态转移。如果你在实践中发现了什么二分查找的刁钻问题也可以顺着这个思路去拆解大概率都能归到“区间不变量 边界更新 单调性”这三大件上。手撕二分没有玄学就是把基础逻辑夯实把该验证的都验证到位剩下的就是熟练度问题了。