刷算法题的人基本都会撞上二分查找而二分查找里最容易被“看似简单、一写就错”绊倒的就是排序数组中的边界问题。很多题库里都有这样两道相邻的题一道要求找出目标值在排序数组中第一次和最后一次出现的位置另一道要求返回目标值应该被插入到数组的哪个下标。这两道题表面上一前一后、互不相干但只要把二分的本质想透了它们根本就是同一道题而且能共用一个极其稳妥的模板。我一直觉得二分查找的关键不是“背模板”而是理解每一轮循环里区间到底在维护什么。这篇文章就从排序数组里的“第一个位置、最后一个位置、搜索插入位置”这三个问题入手把边界二分的思路、手推过程、坑点和统一模板一起讲透。适合刚开始学二分、或者已经会写简单二分但一遇到重复元素就发懵的读者看完之后你至少能稳稳写出不出死循环的二分代码也能在面试里把自己的选择讲明白。1. 两个经典题本质是同一个问题边界定位1.1 为什么“第一个位置 最后一个位置”永远成对出现先还原一下题目场景。有一个升序排列的整数数组比如[1, 2, 3, 3, 3, 5, 7]里面可能存在重复元素。现在给你一个目标值target要求返回它第一次出现的下标和最后一次出现的下标如果数组里根本没有这个值就返回[-1, -1]。很多人的第一反应是这还不简单先线性扫描一遍从头找到第一个等于 target 的下标再从尾找到最后一个等于 target 的下标。这样确实能做对但时间复杂度是 O(n)。在数组长度特别大、或者目标值出现频率特别高的情况下这个解法大概率过不了题目对时间复杂度的限制。而二分查找可以把时间降到 O(logn)这也是这类题真正的考察点。这里有一个非常关键的性质因为数组是升序的所有等于 target 的元素在数组中必然形成一段连续的区间不可能东一个西一个。所以“找第一个位置”和“找最后一个位置”本质上就是在找这段连续区间的左端点和右端点。一旦想通这一点你就会发现这道题不是“找两次元素”而是“找两个边界”两个边界问题用两次二分来解完美契合。1.2 搜索插入位置的隐藏身份再看第二道题。同样是升序排序数组给一个 target要求返回它应该插入的位置插入之后数组依然保持升序。比如[1, 3, 5, 6]如果 target 是 5答案是 2如果 target 是 2答案是 1如果 target 是 7答案是 4如果 target 是 0答案是 0。这道题看起来和“查找第一个/最后一个位置”没有直接关系但它真正的名字叫 lower_bound在有序数组中找到第一个大于等于 target 的元素下标。这个下标同时满足两种语义如果 target 存在这个下标就是它自己的位置如果 target 不存在这个下标就是它应该插入的位置插入后它左边的元素都小于它右边的元素都大于等于它。所以你看34 和 35 这两道题一个在求左右边界一个在求 lower_bound看起来是三类问题实际上都在做同一件事在一个有序序列里通过不断缩小搜索区间定位一个满足特定边界条件的下标。这就是为什么我把它们放在一起讲学一个模板三道题全通。1.3 适合谁来读这篇这篇文章的定位是给那些有一定编程基础、但二分查找总是写得磕磕绊绊的人看的。如果你只是会背一个最简单的二分模板一旦数组里有重复元素就不知道等于 target 时该往哪边收缩那你读完至少能建立起一套自己的不稳定区间思维。如果你是为了面试准备那这篇文章给你的不只是代码还有面试官大概率会追问的“为什么这样收缩”“为什么不会死循环”“mid 为什么这样取”这些细节。2. 二分老写错的根因不变量没守住2.1 二分不是“猜数游戏”是区间收缩很多教程喜欢把二分讲成猜数字游戏每次猜中间大了往左小了往右。这个比喻方便理解但很危险因为它给人一个错觉觉得二分就是“找到一个符合条件的数就停下”。一旦遇到重复元素、要寻找边界或者目标值不存在这种“猜中即停”的思维就会出问题。真正严谨的理解应该是二分每一轮维护的是一个区间这个区间必须始终“包含所有可能成为最终答案的下标”。每比较一次 nums[mid] 和 target我们都能排除掉区间的一半因为根据有序性被排除的那一半里不可能再有答案。只要这个“不变量”——区间始终覆盖所有潜在答案——不被破坏二分就一定是正确的。我见过太多人写二分出错不是因为比较符号写反而是因为不变量在循环过程中被悄悄破坏了。最常见的破坏方式有两种一是更新 left 或 right 时把已经完全确定不可能成为答案的 mid 又塞回区间里二是把区间定义从闭区间改成开区间时left 和 right 的初值、更新规则没有同步调整。2.2 死循环是怎么发生的死循环是二分新手遇到的最大的坑。你写了一个看起来没问题的二分结果程序卡住不动或者在某些输入下疯狂循环。原因很简单循环里 left 和 right 没有向彼此收敛某个边界一直原地踏步。举一个很经典的错误场景。假如你用while (left right)这个循环条件且采用mid (left right) / 2向下取整然后在某种情况下写了left mid。当 left 4, right 5 时mid 4如果走到left mid下一轮还是 left 4, right 5mid 还是 4于是无限循环。这种情况下mid 向下取整导致 left 永远都追不上 right。要解决这个问题有两种思路。第一种是改用向上取整mid left (right - left 1) / 2这样当 left 4, right 5 时 mid 5可以让 left 和 right 真正相遇。第二种更保险的思路是干脆设计一个永远不需要left mid的模板。后面要讲的半开区间模板[left, right)就是这种设计它只使用left mid 1和right mid每轮区间长度严格减小从数学上杜绝了死循环的可能性。2.3 溢出处理二分还有一个看起来很基础、但很多人忽略的细节mid (left right) / 2在 left 和 right 都很大的时候可能溢出。比如 left 和 right 都接近 Integer.MAX_VALUE二者相加就超过 int 的范围了。更稳的写法是int mid left (right - left) / 2;。因为 right 和 left 都是合法数组下标差值不会溢出加上 left 之后依然在 int 范围内。用位运算写成left ((right - left) 1)也行但位运算优先级容易记错我建议就老老实实写除法可读性更好也不容易出幺蛾子。3. 查找第一个等于 target 的位置等于也不放过3.1 从“找任意一个”升级到“找最左边”如果你之前会写经典二分那么你很可能已经习惯这种写法当nums[mid] target时直接 return mid。这个写法在数组里没有重复元素时非常好用一旦有重复元素它只能保证你返回“某一个”等于 target 的下标不能保证是第一个。要让算法返回第一个等于 target 的位置核心改动只有一个当nums[mid] target时不能停要收右边界继续向左搜索。换句话说判断逻辑应该写成“如果 nums[mid] target说明答案可能在 mid 位置或者更左边所以把 right 收到 mid如果 nums[mid] target说明答案一定在 mid 右边所以把 left 收到 mid 1”。这里我们用半开区间写法初始left 0right nums.length循环条件是while (left right)。它的含义是当前搜索区间是[left, right)right 不包含在区间内。退出循环时一定有 left right这个值就是第一个大于等于 target 的下标。3.2 半开区间模板与手推过程以nums [1, 2, 3, 3, 3, 5, 7]target 3为例手推一遍轮次leftrightmidnums[mid]比较结果与动作10733nums[3] 3right 320312nums[1] 3left 232323nums[2] 3right 2结束22--left right返回 2返回 2正好是第一个 3 的下标。注意第 3 轮里 mid 2 时 nums[mid] 等于 target但我们没有停下反而把 right 收到了 2之后 left 也变成了 2区间变成空循环终止。这个“等于也收缩”的操作就是整个左边界查找的灵魂。对应的代码也很简洁int lowerBound(int[] nums, int target) { int left 0, right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }3.3 结束后如何处理lowerBound 返回的是“第一个大于等于 target 的下标”这个下标本身还不能直接作为答案因为 target 可能根本不存在。所以查找第一个位置时代码要补一个判断int first lowerBound(nums, target); if (first nums.length || nums[first] ! target) { return -1; } return first;这个判断同时处理了两种情况数组里没有 targetnums[first] ! target以及 target 比所有元素都大first nums.length。比如数组是[1, 3, 5, 7]target 6lowerBound 返回 3nums[3] 7 ! 6返回 -1正确。4. 查找最后一个等于 target 的位置对偶问题4.1 思路翻转找最后一个等于 target 的位置最直接的对称思路是找到第一个大于 target 的位置然后往前挪一位。这个“第一个大于 target 的位置”在标准库里通常叫 upper_bound。实现上它和 lowerBound 只有一处不同比较条件从nums[mid] target改成nums[mid] target。当nums[mid] target时说明答案可能在 mid 右边或者就是 mid 本身所以把 left 收到 mid 1继续向右搜索当nums[mid] target时把 right 收到 mid。退出时返回的 left就是第一个大于 target 的下标。用同一个数组nums [1, 2, 3, 3, 3, 5, 7]target 3手推一遍轮次leftrightmidnums[mid]比较结果与动作10733nums[3] 3left 424755nums[5] 3right 534543nums[4] 3left 5结束55--left right返回 5返回 5它指向的是数组中第一个大于 3 的元素 5。最后一个等于 target 的下标就是upperBound - 1也就是 4对应数组中最后一个 3正确。代码同样很短int upperBound(int[] nums, int target) { int left 0, right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }4.2 三个细节这里有几个细节值得单独说。第一upperBound 的返回值可能是 0此时upperBound - 1是 -1直接拿去访问数组就会越界。所以拿到右边界后要判断rightIndex 0 rightIndex nums.length nums[rightIndex] target。因为 upperBound 本来表示的是“第一个大于 target 的位置”当它等于 0 说明所有元素都大于 target那么“上一个位置”自然不存在。第二不要试图在同一个二分循环里同时记录“第一个”和“最后一个”。我见过有人试图用两个变量分别保存 candidate然后在一个 while 循环里塞进所有逻辑结果等号方向一多自己先绕晕了。既然左右边界二分一次都是 O(logn)两次二分合起来还是 O(logn)完全没必要为了省一次循环增加理解成本。第三lowerBound 和 upperBound 是一对完美的对偶函数。前者把大于等于 target 的都往左赶后者把小于等于 target 的都往右赶。你在心里记住“lower 找左、upper 找右”这个口诀写代码时方向就不会搞反。4.3 整体封装把左右边界放在一起查找范围的完整代码就是public int[] searchRange(int[] nums, int target) { int first lowerBound(nums, target); if (first nums.length || nums[first] ! target) { return new int[]{-1, -1}; } int last upperBound(nums, target) - 1; return new int[]{first, last}; }空数组的情况也被自动处理了nums.length为 0 时lowerBound 返回 0first nums.length成立直接返回[-1, -1]。5. 搜索插入位置一句话翻译成 lower_bound5.1 极端情况推演搜索插入位置这道题如果你拿[1, 3, 5, 6]这个数组去反推会发现所有情况都能归结为三种target 比所有元素大答案就是数组长度target 比所有元素小答案是 0target 介于两个元素之间答案就是第一个大于等于它的位置。比如target 5数组里有答案 2。target 2数组里没有应该插在 1 和 3 之间答案 1。target 7比所有元素大答案 4。target 0比所有元素小答案 0。这四种情况其实都可以由一个函数统一返回lowerBound(nums, target)。它天然返回第一个大于等于 target 的下标target 存在时就是它自己的位置target 不存在时就是应该插入的位置。5.2 lowerBound 直接当答案所以搜索插入位置的题解几乎就是直接把前面那个 lowerBound 拿过来用public int searchInsert(int[] nums, int target) { int left 0, right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }你会发现一个很有趣的事实这段代码和第三章的 lowerBound 一模一样连返回值都不用加工。这就是为什么我说这两道题本质是同一道题——你在做“查找第一个等于 target 的位置”时先调了 lowerBound再判断存不存在你在做“搜索插入位置”时把 lowerBound 的返回值直接当答案。区别只在于怎么解释这个返回值。5.3 和内置二分的关联如果你用过 Java 的Arrays.binarySearch可能会疑惑它为什么在找不到目标时返回一个负数而且负数的值还很奇怪比如Arrays.binarySearch(new int[]{1, 3, 5, 6}, 2)返回 -2。Java 的规则是这样的如果找到了返回目标下标如果没找到返回-(insertionPoint) - 1。这里的 insertionPoint 就是第一个大于目标值的位置也就是 lowerBound 的返回值。对 target 2 来说lowerBound 1所以返回-1 - 1 -2。之所以要减 1是因为 0 已经被“找到了且下标为 0”占用了必须用负数区分“没找到”和“找到了下标 0”。理解了 lowerBound 之后你再看这个返回值就不会觉得它神秘了它本质上就是把“应插入位置”编码成了一个负数。很多语言的标准库都用类似的约定这个底层逻辑是相通的。6. 一个模板打天下lowerBound upperBound 的收尾封装6.1 最终代码把前面几章的思路整合起来我推荐你直接记住下面这组代码。它只有一个模板套路可以解决查找第一个位置、最后一个位置、搜索插入位置三个问题。public class BinarySearchBound { // 第一个 target 的下标lower_bound public int lowerBound(int[] nums, int target) { int left 0, right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; } // 第一个 target 的下标upper_bound public int upperBound(int[] nums, int target) { int left 0, right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; } // 查找目标值的第一个和最后一个位置 public int[] searchRange(int[] nums, int target) { int first lowerBound(nums, target); if (first nums.length || nums[first] ! target) { return new int[]{-1, -1}; } int last upperBound(nums, target) - 1; return new int[]{first, last}; } // 搜索插入位置 public int searchInsert(int[] nums, int target) { return lowerBound(nums, target); } }6.2 为什么半开区间最不易错我用了一整篇文章来铺垫就是想让你理解最后这个[left, right)半开区间模板的设计逻辑。它的三个特点分别是第一right初始化为nums.length而不是nums.length - 1。这样 left 和 right 一开始就把整个数组都包在搜索区间里不会漏掉最后一个元素。有些闭区间模板写成right nums.length - 1then最后一轮 left 可能越过 right返回时还要考虑边界容易出错。第二退出循环时一定有left right而且这个值可以直接作为答案。不用纠结最后返回 left 还是 right它们相等你怎么写都对。这比闭区间模板在退出后还需要判断 left 是否越界要省心得多。第三更新规则只有两种left mid 1或者right mid。每次更新区间长度都严格变小mid 本身绝不会被留在新区间里除非它正好是新的 right但 right 是不包含在区间内的。所以从这个模板的结构上死循环就被直接排除了。我自己以前也用过闭区间写法代码更短但每次遇到要返回 left 还是 right 的边界问题时总要多想几秒。后来换成半开区间模板稳定用了很久几乎没有再写错过。6.3 复杂度与后续扩展这三道题的时空复杂度完全一致时间 O(logn)空间 O(1)。因为每轮搜索区间缩小一半logn 轮就能结束全程只用了常数个额外变量。学会了这个模板之后你可以把它迁移到很多场景。比如二维矩阵中搜索目标值本质上是把二维坐标映射成一维坐标再用一次二分再比如求一个数的平方根的整数部分可以把这个数看成隐式的有序数组然后二分答案还有旋转排序数组里找最小值、找目标值虽然判断条件需要额外处理但区间收缩的基本骨架是一样的。算法题里最值得投资的往往就是这种能一鱼多吃的核心模板。7. 我的实测建议测试用例、调试手段与理解重心7.1 必测的边界用例算法代码写完不是看一眼觉得对就完事了。我每次写完二分都会跑一遍下面这组边界用例这几类情况几乎覆盖了所有二分查找容易出错的地方测试场景输入target预期结果空数组[]1[-1, -1]/ 插入位置 0单元素等于[3]3[0, 0]/ 0单元素小于[3]2[-1, -1]/ 0单元素大于[3]4[-1, -1]/ 1全相同[2,2,2,2]2[0, 3]/ 0目标在开头[1,1,2,3]1[0, 1]/ 0目标在结尾[1,2,3,3]3[2, 3]/ 2目标不存在且介于中间[1,3,5,6]2[-1, -1]/ 1目标小于最小元素[1,3,5,6]0[-1, -1]/ 0目标大于最大元素[1,3,5,6]7[-1, -1]/ 4我特别提醒全相同这个用例。如果你写的二分在“等于 target 时直接返回”在这个用例下会返回一个中间位置但你要的是第一个和最后一个结果就会错。用上面这个测试表能在 5 分钟之内帮你把代码的边界问题全暴露出来。7.2 调试二分的一个实用技巧如果真的出现死循环或者结果不对我建议别盯着代码空想直接在循环里打印每一轮的 left、right、mid、nums[mid] 和比较方向。比如在 while 循环里加一行日志System.out.println(left left , right right , mid mid , nums[mid] nums[mid] , target target);打印出来后死循环的原因基本一眼就能看出来要么 left 卡在某个值不动要么 right 卡在某个值不动要么 mid 一直等于 left。看到卡住的地方就去检查对应的更新分支是不是把 left 或 right 推回了原位。这把问题定位到具体某一轮循环之后修复就是改一行代码的事。7.3 理解比背模板重要最后说点带个人体会的话。二分查找这个知识点很多人觉得简单但一面试就露馅。原因就在于背模板的人只能写出“标准答案”一旦面试官换了个角度问“为什么等于 target 时你要收缩右边界”或者“如果数组长度是 2 的幂会怎样”就答不上来了。我强烈建议你在理解了这套半开区间逻辑之后自己从零推导一遍不要直接抄代码。推导时反复问自己几个问题我的区间里包含的是哪些下标区间收缩后被排除的那部分里为什么不可能存在答案循环退出时 left 指向的到底是什么语义只要能把这三个问题想通你以后再遇到任何二分的变种题都有底气现场推演而不是祈祷题目和背过的模板吻合。每次面试或者写题遇到二分我都会默念一遍这六个字左边取不到右边取不到。left 更新时加一right 更新时不加一这样区间永远在收缩边界语义也永远清晰。这套模板和思路我用了很久确实是三条题一条路踩过的坑都变成了肌肉记忆。